数据结构考试卷.doc

《数据结构考试卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．组成数据的基本单位是（C）。A.数据项B.数据类型C.数据元素D.数据变量y2．在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的(B)A．直接前趋B．直接后继C．开始结点D．终端结点3．一棵深度为８（根的层次号为１）的满二叉树有（B）个结点。Ａ.256Ｂ.255Ｃ.128Ｄ.124．对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为（C）A.O（n）B.O（1）C.O（n2）D.O（log2n）5．顺序栈的上溢是指（C）A.栈满时作退栈运算B.栈空时作退栈运算C.栈满时作进栈运算C.

2、栈空时作进栈运算6．若有一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（C）A.n-iB.n-i-1C.n-i+1D.不确定7．已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，需（B）次比较可检索成功。A.1B.2C.3D.48．在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法的时间的复杂度是（D）。A.O(1)B.O(n)C.O()D.O(log2n)9．已知一棵度为m的树中有：n1个度为1的结点，n2个度

3、为2的结点，……，nm个度为m的结点，那么该树中共有（B）个叶子结点。A.B.C.D.10．已知数据表A中每个元素距其最终位置不远，则采用（B）排序算法最省时间。A.堆排序B.插入排序C.直接选择排序D.快速排序11．下面算法的时间复杂度为(B)intf(unsignedintn){if(n==0

4、

5、n==1)return1;elsereturnn*f(n-1)}A.O(1)B.O(n)C.O(n2)D.O(n!)12．若让元素1，2，3依次进栈，则出栈次序不可能出现（C）种情况。A.3，2，1B.2，1，3C.3，1，2D.

6、1，3，213．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（B）型调整以使其平衡。A.LLB.LRC.RLD.RR14．已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为（B）A.4B.5C.6D.715．一个算法只能有（C）A．零个或多个输入，零个或多个输出B．一个或多个输入，零个或多个输出C．零个或多个输入，一个或多个输出D．一个或多个输入，一个或多个输出16.线性表的链

7、表存储结构与顺序结构相比优点是（C）A.所有的操作算法实现简单B.便于随机存取C.便于插入和删除D.便于利用零散的存储器空间17.在带有头结点的单链中插入一个新结点时不可能修改（A）A.头指针B.头结点指针域C.开始结点指针域D.其它结点指18.图的广度优先搜索使用的数据结构是（）A.队列B.树C.栈D.集19.一个有向图中所有顶点的度之和等于所有弧的(C)A．4倍　　Ｂ．2倍　　Ｃ．1倍　　　Ｄ．0.5倍20.快速排序算法在最好情况下的时间复杂度为(C)A.O（n）B.O（n2）C.O（nlog2n）D.O（log2n）21

8、．在双向链表中，前趋指针和后继指针分别为prior和next。若要指针p往后移动两个结点，即指向当前结点后继的后继，则需执行语句。若要指针p向前移动一个结点，即指向当前结点的前趋，则需执行语句。p=p->next->next；p=p->prior22．队列的插入操作在进行，删除操作在进行。队尾;队头23．数据的逻辑结构被分为集合结构、线性结构、和。树状结构；图状结构24．下列语句组所代表的算法的时间复杂度为。{for(i=1；i<=n；i++)for(j=1；j<=n；j++)for(k=1；k<=n；k++){s=i+j+k

9、；printf(“%d”，s)；}25.线性表中所含结点的个数称为　　。表长为0的线性表称为　　。线性表的长度(表长),空表26.在一棵树中，（)节点没有前驱节点，()没有后继节点。27．在单链表中，若要插入一个新结点需修改个指针。228．如果要将序列{50，16，23，68，94，70，73}建成堆，则只需把16与相互交换。5029.冒泡排序属于排序方法；堆排序属于排序方法。交换、选择30．在一个具有n个顶点的无向完全图中，包含条边；在一个具有n个顶点的有向完全图中，包含条边。n(n-1)/2、n(n-1)31．已知一棵二叉

10、树的中根序列和后根序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树。32．给定如下所示无向图，（1）写出其邻接矩阵；（2）写出一种以顶点A为起点的深度优先搜索顶点序列。ABEDGCFHAHBDGECF;ABEGDCF;ABDGEHCF等等(只写其中一个)33．以数