2002级数据结构期末试卷A.docVIP

2002级《数据结构》期末试卷A 一、二题答案写在试卷对应答题表中，三、四题答案写在答题纸上 一．判断题（每小题1分，共10分） 1．数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。first-rlink == first（first为表头指针）。 4．出栈序列为abcd，则入栈序列可能是bcda。 5．高级语言中通常利用“递归工作栈”来处理递归。 6．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。对二叉有哪些信誉好的足球投注网站树进行前序遍历，可得到该二叉树所有结点构成的有序序列。n个结点的无向图最多有n*(n-1)条边。 9．一组关键码已完全有序时，最快的排序方法是快速排序。 10．一个索引项对应数据表中一组数据对象的方式叫稀疏索引，稠密索引则是每个索引项对应唯一的数据对象。 1 2 3 4 5 6 7 8 9 10 二．单项选择题（每小题2分，共30分） 1．算法分析的两个方面是____。 A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 A．，n B．，n-1 C．，n D．，n-1 3．对于只在首、尾两端进行插入操作的线性表，宜采用的存储结构为_____。 A．顺序表 B．用头指针表示的单循环链表 C．单链表 D．用尾指针表示的单循环链表 4．现有一带表头结点的单链表，若要在结点p的后面插入结点q，则需要执行_____。 A．q-link = p; p-link = q; B．p-link = q; q-link = p-link; C．q-link = p-link; p-link = q; D．p-link = q-link; q-link = p; 5．分别用front和rear表示顺序循环队列的队首和队尾指针，则判断队空的条件是___。 A．front+1==rear B．(rear+1) % maxSize == front C．front==0 D．front==rear 6． 广义表A=( a, b, ( c, d ), ( e, ( f, g ) ) )，则Head( Tail( Head( Tail( Tail( A ) ) ) ) ) 的值为 。 A. (g) B. (d) C. c D. d 7．一个二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是 。 A. CABDEFG B. BCDEAFG C. DBACEFG D. EBACDFG 8．高度为h的满二叉树(仅含根结点的二叉树高度为零)的结点数是多少 。 A.h＋1 B.2h＋1 C.2h+1－1 D.2h 9依次插入序列(50，72，43，85，75，20，35，45，65，30)后建立的二叉有哪些信誉好的足球投注网站树中，查找元素35要进行_____元素间的比较。 A.4次 B.5次 C.7次 D.10次 10. 在一个空AVL树内，依次插入关键字：49, 94, 91, 47, 92, 45, 89, 42, 87，删除旋转类型__________。 A. B.左右双旋 C.右单旋 D.其它情况 11．关键路径是结点网络中_____。 A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 12．如图所示的无向图，从顶点v1开始进行深度优先遍历，可得到的顶点访问序列是______。 A.1 2 3 4 5 6 7 B.1 2 4 3 5 6 7 C.1 2 4 5 6 3 7 D.1 2 4 3 5 7 6 13．在基于关键码比较的排序算法中，______算法在最坏情况下，关键码比较次数不高于O(nlog2n)。 A. 起泡排序 B. 直接插入排序 C. 二路归并排序 D. 快速排序 14．对数据元素序列( 49, 72, 68, 13, 38, 50, 97, 27 )排序，前三趟排序结束时的结果依次为： 第一趟：13, 72, 68, 49, 38, 50, 97, 27； 第二趟：13, 27, 68, 49, 38, 50, 97, 72； 第三趟：13, 27, 38, 49, 68, 50, 97, 72； 该排序采用的方法是_________。 A. 直接插入排序 B. 直接选择排序 C. 冒泡排序 D. 堆排序 15．在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_______。 A. B