：名姓 装 订 ： 线号学 ：级班 哈尔滨工程大学试卷 考试科目: 数据结构 A卷 题号 一 二 三 四 五 六 总分 分数 评卷人 一、单项选择题（每空1分，共20分） 1．以下数据结构中， 是非线性数据结构。 A．树 B．字符串 C．队 D．栈 2．对于顺序存储的线性表，访问结点和删除结点的时间复杂度分别为 。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 3．循环链表H的尾结点指针P的特点是 。 A．P->NEXT==H B．P->NEXT== H->NEXT C．P==H D．P==H->NEXT 4．依次读入数据元素序列abcdefg进栈，每进一个元素，机器可要求下一个元素进栈或出栈，如此进行，则栈空时弹出的元素构成的序列是 。 A．decfbga B. fegdacb C. efdgbca D. cdaefbg 5．由两个栈共享一片连续的内存空间时，应将两栈的栈底分别设在这片内存空间的两端，这样，当 时才产生上溢。 A. 两个栈的栈顶同时到达栈空间的中心点。 B. 其中一个栈的栈顶到达栈空间的中心点。 C. 两个栈的栈顶在栈空间的某一位置相遇。 D. 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底。 第1页 共6页 6．假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为 。 A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 7．数组A[0..5][0..6]的每个元素占五个字节，将其按列序为主序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是 。 A. 1175 B. 1180 C. 1205 D. 1210 8．已知广义表: A=(a,b)，B=(A,A)，C=(a,(b,A),B)，运算tail(head(tail(C))) 的结果是 。 A.（a） B. A C. a D. (A) 9．算术表达式A+B*C-D/E转为后缀表达式后为 。 A．-A+B*C/DE B. -+A*BC/DE C．-+*ABC/DE D. ABC*+DE/- 10．在一棵三叉树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为 个。 A．4 B．5 C．6 D．7 11．一棵具有 n个结点的完全二叉树的高度是 。 A．logn+1 B．logn+1 C．logn D．logn-1 12．引入线索二叉树的目的是 。 A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 13．下面关于求关键路径的说法不正确的是 。 A．求关键路径是以拓扑排序为基础的。 第2页 共 6页 B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同。 C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差。 D．关键活动一定位于关键路径上。 14．无向图G=(V,E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e), (c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是 。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 15．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是 。 A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 16．设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有 个记录。 A．1 B. 2 C. 3 D. 4 17．下列排序算法中， 是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 18．对序列{15,9,7,8,20,-1,4} 用希尔排序方法排序，经一趟后序列变为{15, -l,4,8,20,9,7}则该次采用的增量是 。 A. l B. 4 C. 3 D. 2 第3页 共6页 19．对关键码序列28，16，32，12，60，2，5，72快速排序（选第一个记录为枢轴），从小到大一次划分结果为 。 A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72) C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72) 20．在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是 。 A. 选择 B. 冒泡 C. 插入 D. 堆 二、填空题（每空1分，共10分） 1．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}，请写出按2路归并排序方法对该序列进行一趟扫描后的结果 。 2．在有序表A[1…20]中，按折半查找方法进行查找，查找长度为4的元素的下标从小到大依次是 。 3．求图的最小生成树有两种算法， 算法适合于求稠密图的最小生成树。 4．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为 。 5．具有n个结点的满二叉树，其叶结点的个数是 。 6．带头结点的双循环链表L中只有一个元素结点的条件是 。 7. 一个深度为k，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依次对结点编号，则编号最小的叶子的序号是 。 8．127阶B-树中每个结点最多有 个关键字。 9．可以唯一的标识一个记录的关键字称为 。 10．假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A[9][9]在B中的存储位置k= 。（矩阵元素下标从1开始） 三、判断题（每空1分，共10分） 1．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 第4页 共 6页 装 订 线 本文来源：https://www.wddqw.com/doc/53da858cb107e87101f69e3143323968001cf495.html