《数据结构》自测题.docVIP

《数据结构》自测题1 一、单选题 1、从一棵二叉有哪些信誉好的足球投注网站树中查找一个元素时,其时间复杂度大致为( )。 A、O(1) B、O(n) C、O(log2n) D、O(n2) 2、向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A、O(n) B、O(1) C、O(n2) D、O(log2n) 3、n个顶点的强连通图中至少含有( )。 A、n-l条有向边 B、n条有向边 C、n(n-1)/2条有向边 D、n(n-1)条有向边 4、在一个单链表HL中,若要向表头插入一个由指针p指向的结点,则执行( )。 A、HL=p; p-next=HL B、p-next=HL;HL=p; C、 p-next=HL;p=HL; D、 p-next=HL-next;HL-next=p 5、当一个作为实际传递的对象占用的存储空间较大并可能需要修改时,应最好把它说明为( )参数,以节省参数值的传输时间和存储参数的空间。 A、整型 B、引用型 C、指针型 D、常值引用型 二、填空题 1、在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同,各自分别为 域和 域。 2、表示图的三种存储结构为 、 和 。 3、数据的存储结构被分为 、 、 和 四种。 4、在一棵二叉有哪些信誉好的足球投注网站树中,每个分支结点的左子树上所有结点的值一定 该结点的值,右子树上所有结点的值一定 该结点的值。 5、对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时,其时间复杂度为 ,对用邻接表表示的图进行任一种遍历时,其时间复杂度为 。 6、 中缀表达式3+x*(2.4/5-6)所对应的后缀表达式为 。 7、假定一棵二叉树的结点数为18,则它的最小深度为 ,最大深度为 。 8、从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时,其查找长度分别为 和 。 三、运算题。 1、已知一个带权图的顶点集V和边集G分别为： V={0,1,2,3,4,5}; E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(4,5)10}, 则求出该图的最小生成树的权。 2、有7个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点生成一棵哈夫曼树,求出该树的带权路径长度、高度、双分支结点数。 带权路径长度： 高度： 双分支结点数： 。 四、阅读算法,回答问题。 1、void AG(Queue Q) { InitQueue(Q); int a[5]={6,12,5,15,8}; for(int i=0;i5;i++) QInsert(Q,a[i]); QInsert(Q,QDelete(Q)); QInsert(Q,20); QInsert(Q,QDelete(Q)+16); while(!QueueEmpty(Q)) coutQDelete(Q)’’; } 该算法被调用执行后,得到的输出为： 2、void AC(List L) { InitList(L); InsertRear(L,25); InsertFront(L,50); int a[4]={5,8,12,15,36}; for(int i=0;i5;i++) if(a[i]%2==0) InsertFront(L,a[i]); else InsertRear(L,a[i]); } 该算法被调用执行后,得到的线性表L为： 五、算法填空,在画有横线的地方填写合适的内容。 1、已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode{ ElemType data; BinTreeNode *left,*right }; 其中data为结点值域,left和right分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树BT中值为X的结点所在的层号,请在划有横线的地方填写合适内容。 int NodeLevel(BinTreeNode *BT,ElemType X) { if(BT==NULL) return 0; //空树的层号为0 else if(BT-data==