合肥工业大学研究生软件技术基础总复习题及参考答案

i i一、 选择题软件技术基础 总复习题及参考答案1、 线性表若是采用链式存储结构时，要求内存中可用存储单元的地址 D 。

A 、必须是连续的 B 、部分地址必须是连续的C 、一定是不连续的D 、连续或不连续都可以2、 栈和队列都是 B 。

A 、顺序存贮的线性结构B 、限制存取点的线性结构C 、链接存贮的线性结构 D 、限制存取点的非线性结构3、 与线性表的链接存贮不相符合的特性是 C 。

A 、便于插、删运算 B 、存贮空间动态分配 C 、需要连续的存贮空间 D 、只能顺序查找4、 设二叉树的根为第一层，则第 i 层上的结点数最多有 d 。

A 、２B 、２ +1C 、２i-１ D 、２i -1 5、 如将一棵有 n 个结点的完全二叉树按顺序存放方式，存放在下标编号为 0, 1,…, n-1的一维数组中，设某结点下标为 k (k>0)，则其双亲结点的下标是 A 。

A 、(k-1)/2B 、(k+1)/2C 、k/2D 、k-16、 由权值分别为 3,8,6,2,5 的叶子结点生成一棵霍夫曼树，它的带权路径长度为 A 。

A 、53B 、48C 、72D 、247、 设 I 和 O 分别表示入栈和出栈操作，栈的初态和终态都为空，则下列操作序列 合法的有_ D_ _。

A 、IOIOOIOIB 、IOOIOIIOC 、IIIOIOIOOD 、IIOIIOOO8、 二叉树的前序序列为 E FHIGJK ，中序序列为 H FIEJKG ，则二叉树的根为 C 。

A 、KB 、GC 、ED 、H9、 对有序表{ -1, 0, 1, 3, 4, 6, 8, 10, 12 }进行折半查找，则查找 12 需要 比较的次数为 B 。

A 、3B 、4C 、5D 、610、 在一个单链表中，若 q 结点是 p 结点的前驱结点，若在 q 与 p 之间插入结点 s ， 则执行 D 。

A 、s→link = p→link; p→link = s;B 、p→link = s; s→link = q;C 、p→link =s→link; s→link = p; D 、q→link = s; s→link = p ;11、 一个栈的入栈序列为 a ，b ，c ，则出栈序列不可能的是 C 。

A 、c,b,a B 、b,a,cC、c,a,bD、a,c,b12、如果将一棵有 n 个结点的完全二叉树按层次遍历次序，存放在下标编号为0,1, … ,n-1 的一维数组中，设某结点下标为k( k 0 )，如果其左孩子存在，则其左孩子结点的下标是 C 。

A、2k– 1B、2kC、2k + 1D、2k + 213、用整数5, 7, 3, 6, 4 作为五个树叶的权值，可以构造一棵带权路径长度值为C 的霍夫曼树。

A、78B、62C、57D、2514、设单链表中结点结构为(data,link)，若想删除结点*p 的直接后继，则应执行下列哪一个操作 A 。

A、p->link=p->link->link;B、p=p->link; p->link=p->link->link;C、p->link=p->link; D、p=p->link->link;15、顺序表是线性表的 B 。

A、链式存储结构 B、顺序存储结构C、索引存储结构D、散列存储结构 16、若某线性表中最16、常用的操作是取第i个元素和找第i个元素的前趋元素，则采用 A 存储方式最节省时间。

A、顺序表B、单链表C、双链表D、单循环链表17、当利用大小为n的数组顺序存储一个栈时，假定用t op= =n 表示栈空，则向这个栈插入一个元素时，首先应执行 B 语句修改 top 指针。

A、top++;B、top--;C、top=0;D、top;18、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则 AA、n0= n2+1B、n2= n0+1C、n0= 2n2+1D、n2=2n0+119、具有 35 个结点的完全二叉树的深度为 A 。

A、5B、6C、7D、820、在有向图中，所有顶点的入度之和是所有顶点出度之和的 B 倍。

A、0.5B、1C、2D、421、若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行 B 次比较。

A、33B、45C、70D、9122、对含有B 个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

A、0B、1C、2D、不存在这样的二叉树23、数据结构是一门研究非数值计算的程序设计问题中计算机的 A 以及它们之间的 B 和运算等的学科。

① A.数据元素 B.计算方法 C.逻辑存储 D.数据映像② A.结构 B.关系 C.运算 D.算法24、数据结构在计算机内存中的表示是指 A 。

A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系25、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。

A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法26、在数据结构中，从逻辑上可以把数据结构分成 C 。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构 27、带头结点的单链表 head 为空的判定条件是 B 。

A. head= =NULLB. head->next= =NULLC. head->next= =headD. head !＝ NULL 28、在循环双链表的p所指结点之前插入s所指结点的操作是 D 。

A. p->prior=s；s->next=p；p->prior>next=s；s->prior=p->prior；B. p->prior=s；p->prior->next=s；s->next=p；s->prior=p->prior；C .s->next=p；s->prior=p->prior；p->prior=s；p->right->next=s； D. s->next=p；s->prior=p->prior；p->prior>next=s；p->prior=s；29、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。

A.单链表B.静态链表C.线性链表D.顺序存储结构 30、栈和队列的共同点是 C 。

A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点 31、向一个栈顶指针为h s 的链栈中插入一个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;32、判定一个环形队列 qu（最多元素为 MaxSize ）为空的条件是 C 。

A. qu->rear-qu->front= =MaxSize B. qu->rear-qu->front-l==MaxSize C. qu->front==qu->rear D. qu->front= =qu->rear+l33、若用一个大小为 6 的一维数组来实现环形队列，且当前 rear 和 front 的值分别为0 和3。

当从队列中删除一个元素，再加入两个元素后，rear 和f ront 的值分别是B 。

A. 1 和5B. 2 和4C. 4 和2D. 5 和134、在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算是 C。

A. r=f->next;B. r=r->next;C. f=f->next;D. f=r>next; 35、下图所示二叉树的中序遍历序列是 B 。

A. abcdgefB. dfebagcC. dbaefcgD. defbagc36、深度为 5 的二叉树至多有 C 个结点。

A. 16B. 32C. 31D.1037、对一个满二叉树，m 个树叶，n 个结点，深度为 h，则 D 。

A. n=h+mB. h+m=2nC. m=h-1D. n=2h-138、下列说法正确的是 A 。

A、链栈没有容量限制B、顺序栈没有容量限制 C、链队有容量限制 D、单向链表有容量限制39、在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。

A. 1/2B. 1C. 2D. 440、对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是D 。

A. nB. (n-1)2C. n-1D. n241、已知一个图如下图所示，若从顶点 a 出发按深度搜索法进行遍历，则可能得到的一种顶点序列为 D ；按广度搜索法进行遍历，则可能得到的一种顶点序列为 B 。

① A. a，b，e，c, d，f B. a，c，f，e，b，dC. a，e，b，c，f，dD. a，e，d，f，c，b② A. a，b，c，e，d，f B. a，b，c，e，f，dC. a，e，b，c，f，dD. a，c，f, d，e，b42、顺序查找法适合于存储结构为 B 的线性表。

A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储43、采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为 D 。

A.O(n2)B.O(nlog2 n)C.O(n)D. O(log2n)44、对有 18 个元素的有序表作折半查找，则查找 A[3] 的比较序列的下标为 D 。

A. 1、2、3B.9, 5、2、3C.9、5、3D.9, 4、2、345、有一数列2、3、4、5，按2、3、4、5 顺序入队，出队的顺序是 A 。

A. 2345B. 3245C. 5342D. 243546、在排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 C 。

A.希尔排序B.冒泡排序C.插入排序D.选择排序47、在下列算法中， C 算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。

A.堆排序B.冒泡排序C.插入排序D.快速排序48、在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为 D 。

A. O(1)B.O (log2n)C. O(n2)D. O(n) 49、在决定选取何种存储结构时，一般不考虑 A 。