班级： 学号： 姓名： 装 订 线哈尔滨工程大学试卷考试科目: 数据结构 A卷 题号一二三四五六总分分数评卷人一、单项选择题（每空1分，共20分）1以下数据结构中， 是非线性数据结构。A树 B字符串 C队 D栈 2对于顺序存储的线性表，访问结点和删除结点的时间复杂度分别为 。AO(n) O(n) B. O(n) O(1)C. O(1) O(n) D. O(1) O(1)3循环链表H的尾结点指针P的特点是 。AP-NEXT=HBP-NEXT= H-NEXT CP=H DP=H-NEXT4依次读入数据元素序列abcdefg进栈，每进一个元素，机器可要求下一个元素进栈或出栈，如此进行，则栈空时弹出的元素构成的序列是 。Adecfbga B. fegdacbC. efdgbca D. cdaefbg5由两个栈共享一片连续的内存空间时，应将两栈的栈底分别设在这片内存空间的两端，这样，当 时才产生上溢。A. 两个栈的栈顶同时到达栈空间的中心点。B. 其中一个栈的栈顶到达栈空间的中心点。C. 两个栈的栈顶在栈空间的某一位置相遇。D. 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底。6假设以数组Am存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为 。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m7数组A0.50.6的每个元素占五个字节，将其按列序为主序存储在起始地址为1000的内存单元中，则元素A55的地址是 。A. 1175 B. 1180 C. 1205 D. 12108已知广义表: 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/DEC-+*ABC/DE D. ABC*+DE/-10在一棵三叉树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为 个。A4B5 C6 D7 11一棵具有 n个结点的完全二叉树的高度是 。Alogn+1 Blogn+1 Clogn Dlogn-112引入线索二叉树的目的是 。A 加快查找结点的前驱或后继的速度 B 为了能在二叉树中方便的进行插入与删除C 为了能方便的找到双亲 D 使二叉树的遍历结果唯一13下面关于求关键路径的说法不正确的是 。 A求关键路径是以拓扑排序为基础的。 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)，对该图进行深度优先遍历，得到的顶点序列正确的是 。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b15分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是 。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的链中有 个记录。A1 B. 2 C. 3 D. 417下列排序算法中， 是稳定的。 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. 219对关键码序列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在有序表A120中，按折半查找方法进行查找，查找长度为4的元素的下标从小到大依次是 。3求图的最小生成树有两种算法， 算法适合于求稠密图的最小生成树。4如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为 。5具有n个结点的满二叉树，其叶结点的个数是 。6带头结点的双循环链表L中只有一个元素结点的条件是 。7. 一个深度为k，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依次对结点编号，则编号最小的叶子的序号是 。8127阶B-树中每个结点最多有 个关键字。9可以唯一的标识一个记录的关键字称为 。10假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A99在B中的存储位置k= 。（矩阵元素下标从1开始）三、判断题（每空1分，共10分）1顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )2通常使用队列来处理函数或过程的调用。( )3数组不适合作为任何二叉树的存储结构。( )4一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。( )5必须把一般树转换成二叉树后才能进行存储。( )6无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。( )7在二叉树排序树中插入一个新结点，总是插入到叶结点下面。( )8采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。( )9当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。 ( )10快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。 ( ) 四、应用题（每题5分，共30分）1对字符序列t,d,e,s,u,g,b,j,a,k,r,i，构成一棵平衡二叉（排序）树，并为每一次的平衡处理指明旋转类型。（要求画出建树过程）2设有一组关键字1,13,12,34,38,33,27,22，采用哈希函数H（key）= key mod 11和线性探测再散列法解决冲突，对该关键字序列构造表长为11哈希表。3给出一组关键字12,2,16,30,8,28,4,10,20,6,18，写出用下列算法从小到大排序时第一趟结束时的序列： 希尔排序（第一趟排序的增量为5） 快速排序（选第一个记录为枢轴）4假定用于通讯的电文仅由8个字母C1、C2、C3、C4、C5、C6、C7、C8组成，各个字母在电文中出现的频率分别为0.05、0.25、0.03、0.06、0.10、0.11、0.36、0.04，试为这8个字母设计哈夫曼编码。5一棵二叉树的先序序列为ABDFCEGH，中序序列为BFDAGEHC，画出这棵二叉树的后序线索树。6.用克鲁斯卡尔算法构造下图的一棵最小生成树，并给出选边顺序。12564318412810202515523767五、算法设计题（每题15分，共30分）1设计算法，统计一棵二叉树中所有叶结点的数目及非叶结点的数目。2已知一个不带头结点的双向循环链表（H为指向第一个结点的指针），从第二个结点至表尾递增有序。试编写程序，将第一个结点删除并插入表中适当位置，使整个链表递增有序。（设第二个结点数据域的值第一个结点数据域的值表尾结点数据域的值）。链表的结点结构如下： typedef struct DuLNode ElemType data; Struct DuLNode *prior; Struct DuLNode *next; DuLNode, *DuLinkList;第5页 共6页第6页 共 6页