数据结构总复习习题讲解

数据结构习题讲解2013年11月

数据结构总复习习题讲解

一、选择题

1.在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一 个新元素时，需向后移动 B 个元素。 A. n-1 B. n-i+1 C. n-i-1 D. i 2.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底， 以top作为栈顶指针， 则当做出栈处理时，top变化为 C 。 A. top不变 B. top= -n C. top=top-1 D. top=top+1 5.若进栈序列为1,2,3,4,进栈过程中可以出栈，则 C 不可能是 一个出栈序列。 A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4 7.在具有n个单元的顺序存储的循环队列中，假定front和rear分 别为队首指针和队尾指针，则判断队满的条件是 D 。 A. rear % n= =front B. (rear-1) % n= =front C. (rear-1) % n= =rear D. (rear+1) % n= =front

数据结构总复习习题讲解

9.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和 *p之间插入*s结点， 则执行 C 。 A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p; C. q->next=s; s->next=p; D. p->next=s; s->next=q; 10.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行 C 。 A. hs->next=s; B. s->next=hs->next; hs->next=s; C. s->next=hs;hs=s; D. s->next=hs; hs=hs->next; 11.在一个链队列中，假定front和rear分别为队首指针和队尾指针， 则进行插入*s结点的操作时应执行 B 。 A. front->next=s; front=s; B. rear->next=s; rear=s; C. front=front->next; D. front=rear->next; 14.线性表采用链式存储时，其地址 D 。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续与否均可以

数据结构总复习习题讲解

15.设单链表中指针p指着结点(数据域为m),指针f指着将要插 入的新结点(数据域为x),当x插在结点m之后时，只要先修改 B 后修改p->link=f即可。 A. f->link=p; B. f->link=p->link; C. p->link=f->link; D. f=nil; 16.在双向链表存储结构中，删除p所指的结点时需修改指针 B 。 A. ((p->prior) ->next) -> prior =p; p-> next =(p-> next) -> next; B. (p-> prior) -> next =p-> next; (p-> next) -> prior =p-> prior; C. p-> prior =(p-> prior) -> prior; ((p-> prior) -> prior) -> next =p; D. ((p-> prior) -> prior) -> next =p; p-> prior =(p-> prior) -> prior; 17.在双向链表存储结构中，删除p所指的结点的前趋结点(若 存在)时需修改指针 A 。 A. ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink; B. ((p->rlink) ->rlink) ->llink=p; p->rlink=(p->rlink) ->rlink; C. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink; D. p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p;

数据结构总复习习题讲解

20.二分法查找 A 存储结构。 A. 只适用于顺序 B. 只适用于链式 C. 既适用于顺序也适用于链式 D. 既不适合于顺序也不适合于链式 21.在线性表的链式存储结构中，逻辑上相邻的元素在物理位 置上 B 。 A. 一定相邻 B. 不一

定相邻 C. 有时相邻 22.设字符串s1='abcdefg',s2='pqrst',则运算 s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值为 D 。 A. 'bcdef' B. 'bcdefg' C. 'bcpqrst' D. 'bcdefef' 23.假定在一棵二叉树中，双分支结点数为15个，单分支结点 数为32个，则叶子结点 数为 B 。 A. 15 B. 16 C. 17 D. 47 24.假定一棵二叉树的结点数为18个，则它的最小高度 B 。 A. 4 B. 5 C. 6 D. 18

数据结构总复习习题讲解

25.在一棵二叉树中第五层上的结点数最多为 C 。 A. 8 B. 15 C. 16 D. 32 26.在一棵具有五层的满二叉树中，结点总数为 A 。 A. 31 B. 32 C. 33 D. 16 27.已知8个数据元素为(34、76、45、18、26、54、92、65), 按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的 结点总数为 B 。 A. 1 B. 2 C. 3 D. 4 28.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼 树，该树的带权路径长度为 C 。 A. 23 B. 37 C. 44 D. 46 31.如果结点A有三个兄弟，而且B是A的双亲，则B的出度是 B 。 A. 3 B. 4 C. 5 D. 1 33.在完全二叉树中，当i为奇数且不等于1时，结点i的左兄弟 是结点 D ,否则没有左兄弟。 A. 2i-1 B. i+1 C. 2i+1 D. i-1

数据结构总复习习题讲解

34.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进 行编号，编号值为1,2,…,n且有如下性质：T中任一结点V,其编号等 于左子树上的最小编号减1,而V的右子树 的结点中，其最小编号 等于V右子树上结点的最大编号加1。这时按 B 编号。 A. 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次遍历序列 35.在一个有向图中，所有顶点的入度之和等于所有顶点的出度 之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4 36.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示， 则表头向量的大小 为 A 。 A. n B. n+1 C. n-1 D. n+e 37.具有n个顶点的无向完全图，边的总数为 D 条。 A. n-1 B. n C. n+1 D. n*(n-1)/2 39.最小代价生成树 D 。 A.是唯一的 B.不是唯一的 C.唯一性不确定 D.唯一性与原图边的权值有关

数据结构总复习习题讲解

40.在无向图G的邻接矩阵A中，若A[i,j]等于1,则A[j,i]等于 C 。 A. i+j B. i-j C. 1 D. 0 42.已知一个有序表为(12、18、24、35、47、50、62、83、90、 115、134),当二分查找值为90的元素时， B 次比较后查找成功； 当二分查找值为47的元素时， D 次比较后查找成功。 A. 1 B. 2 C. 3 D. 4 43.散列函数有一个共同性质，即函数值应当以 D 取其值域的 每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 44.设散列地址空间为0~m-1,k为关键字，用p去除k,将所得的 余数作为k的散列地址，即H(k)=k % p。为了减少发生冲突的频率， 一般取p为 D 。 A. 小于m的最大奇数 B. 小于m的最大偶数 C. m D. 小于m的最大素数

数据结构总复习习题讲解

48.一组记录排序码为(46、7

9、56、38、40、84),则利用堆排 序的方法建立的初始堆为 B 。 A. (79、46、56、38、40、80) B. (84、79、56、38、40、46) C. (84、79、56、46、40、38) D. (84、56、79、40、46、38) 49.一组记录的关键码为(46、79、56、38、40、84),则利用快 速排序的方法，以第一个记录为基准得到的一次划分结果为 C 。 A. (38、40、46、56、79、84) B. (40、38、46、79、56、84) C. (40、38、46、56、79、84) D. (40、38、46、84、56、79) 50.在平均情况下快速排序的时间复杂性为 C ,空间复杂性 为 B ;在最坏情况下(如初始记录已有序),快速排序的时 间复杂性为 D ,空间复杂性为 A 。 A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 ) P276

数据结构总复习习题讲解

二、填空题 3.一个数据结构用二元组表示时，它包括 [1] 数据元 素 的集合K和K上 [2]二元关系 的集合R。 5.对于顺序存储的线性表，当随机插入或删除一个元 素时，约需平均移动表长 [1] 一半 的元素。 6.对于长度为n的顺序表，插入或删除元素的时间复 杂性为 [1] O(n) ;对于顺序栈或队列，插入或删除元素 的时间复杂性为 [2] O(1) 。 7.在具有n个单元、顺序存储的循环队列中，队满时 共有 [1] n-1 个元素。 9.在线性表的顺序存储中，元素之间的逻辑关系是通 过 [1] 相邻位置 决定的；在线性表的链接存储中，元 素之间的逻辑关系是通过 [2] 链接指针 决定的。

数据结构总复习习题讲解

10.一个单链表中删除*p结点时，应执行如下操作: p q (1)q=p->next; (2)p->data=p->next->data; (3)p->next= [1] q->next或p->next->next ; (4)free(q); 11.若要在一个单链表中的*p结点之前插入一个*s结 点时，可执行如下操作: p (1)s->next= [1] p->next ; (2)p->next=s; (3)t=p->data; (4)p->data= [2] s->data ; s (5)s->data= [3] t ;

数据结构总复习习题讲解

13.无论对于顺序存储还是链接存储的栈和队列来说，进行插入 或删除运算的时间复 杂性均相同，则为 [1] O(1) 。 15.对于一棵具有n个结点的树，则该树中所有结点的度之和为 n1 。 16.在一棵二叉树中，度为0的结点的个数为n0 ,度为2的结点的 个数为n2 ,则：n0 = n2 +1 。 17.在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点 的下标为 [1] 2 , 若它存在左孩子，则左孩子结点的下标为 [2] 10 , 若它存在右孩子，则右孩子结点的下标为 [3] 11 。 19.在一棵二叉排序树中，按 中序 遍历得到的结点序列是一个 有序序列。 20.由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树， 则带权路径长度为 55 。

数据结构总复习习题讲解

21.假定在二叉树的链接存储中，每个结点的结构为 left data right ,其中

data为值域，left和right分别为链接左、右孩子结点的指针域， 请在下面中序遍历算法 中画有横线的地

方填写合适的语句。 void inorder(bt); { if (bt) { (1) [1] inorder(bt->left) ; (2) [2] printf(bt->data) ; (3) [3] inorder(bt->right) ;} } 23.假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的 空间复杂性为 [1] O(n2 ) , 采用邻接表表示的空间复杂性为 [2] O(n+e) 。

数据结构总复习习题讲解

25.已知一个图如下所示，在该图的最小生成树中，各边的权值 之和为 20 。 ① 10 ② 15 5 2 8 ⑤ 12 ③ 3 ④ 26.假定在有序表A[1..20]上进行二分查找，则比较一次查找成功 的结点数为 [1]1 , 比较两次查找成功的结点数为 [2]2 ,比较三次 查找成功的结点数为 [3]4 ,比较四次查找成功结点数为 [4]8 ,比较 五次查找成功的结点数为 [5]5 ,平均查找长度为 [6]3.7 。

数据结构总复习习题讲解

28.在散列存储中，装填因子α的值越大，存取元素时 发生冲突的可能性就 [1] 越大，当α的值越小，存取元 素时发生冲突的可能性就 [2] 越小 。 29.给定线性表(18,25,63,50,42,32,90),用散列方式存 储，若选用h(K)=K % 9作为散列函数，则元素18的同义 词元素共有 [1]2 个，元素25的同义词元素共有 [2]0 个， 元素50的同义词元素共有 [3]1 个。 30.在对一组记录 (54,38,96,23,15,72,60,45,83)进行 直 接选择排序时，第四次选择和交换后，未排序记录(即 无序表)为 (54,72,60,96,83) 。 33.在直接插入和直接选择排序中，若初始数据基本 正序，则选用 [1] 直接插入排序 ，若初始数据基本反 序，则选用 [2] 简单选择排序 。

数据结构总复习习题讲解

34.在堆排序、快速排序和归并排序中，若只从 节省空间考虑，则应首先选取 [1] 堆排序 方法， 其次选取 [2] 快速排序 方法，最后选取 [3] 归 并排序 方法；若只从排序结果的稳定性考虑， 则应选取 [4] 归并排序 ；若只从平均情况下排 序最快考虑，则应选取 [5] 快速排序 方法；若 只从最坏情况下排序最快并且要节省内存考虑， 则应选取 [6] 堆排序 方法。