数据结构试卷

1、数据结构考卷课程名称数据结构使用专业管理科学与工程班级姓名学号 一、单项选择题（每题 2 分，共 40 分）1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行和删除运算，则利用（A顺序表）方式最节省时间。B双链表 D单循环链表N 的数组空间中，若该队列的队首和队尾C结点的双循环链表2.一个队列顺序在一个长度为指针分别用 front 和 rear 表示，则该队列中的元素个数为（）。A(rear+N)%N C(rear-front+N)%N一个栈的输入序列为B(rear-front)%N D(front+N)%N123n，若输出序列的第一个元素是 n，输出第 i3.（1<=i&l

2、t;=n）个元素是（）。A不确定Bn-i+1CiDn-i4.若语句 S 的执行时间为O(1)，那么下列程序段的时间复杂度为（ For(i = 0; i <= n ; i+)For(j = 0; j <=n ;j+)S;）。BO(n2)AO(n)利用二叉链表A指向最左孩子C空CO(n*log2n)DO(n*i)5.树，则根结点的右指针是()B指向最右孩子D非空6.由权值分别为 3，8，10，2，6 的叶子结点生成一棵哈夫曼树，则其中非终端结点数为（A2）。B3C4D57.设树T 的度为 5，其中度为 1，2，3，4 和 5 的结点个数分别为 5，4，3，2，1 则T 中的叶子结点数为

3、（）。A19B20C21D221试题得分一二三四五总分8.n 个结点的二叉树上空指针数目为（）CnlA2nBnlDn9.已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果为（）。ACBEFDAB FEDCBAC CBEDFAD不定10.具有 65 个结点的完全二叉树的高度为（）（根的层次号为 1）。A8B7C6D911.设有 6 个结点的无向图，该图至少应有()条边才能确保是通图。A5在有向图的邻接表A顶点 v 的度C顶点 v 的入度B6C7D812.结构中，顶点 v 在链表中出现的次数是（B顶点 v 的出度D依附于顶点 v 的边数）。13.数据表中有

4、 10000 个元素，如果仅要求求出其中最大的 10 个元素，则采用（ ）算法最节省时间。A堆排序C快速排序二分查找法适用于B希尔排序 D直接选择排序）的、按关键字排好序的线性表。B顺序D链式14.结构为（A顺序C索引或链式15.现存在一个有序表为(10,15,17,18,25,29,48,52,58,69,90)，当二分查找值为 58的元素时，(A1)次比较后方可查找B2。C3D416.散列表的地址区间为 0-17，散列函数为 H(K)=K mod 17。采用线性探测法处理，并将关键字序列 (26,25,72,38,8,18,59)依次到散列表中。查找元素 59 需要搜索的次数是（）。A2B

5、3C4D517.对下列关键字序列用快速排序法进行排序时，速度最快的排序方法是（）。A (5,9,17,21,23,25,30)C (21,25,5,17,9,23,30)B (21,9,17,30,25,23,5)D (25,23,30,17,21,5,9)18.一组的排序码为46,79,56,38,40,84，则利用大根堆排序的方法建立的初始堆为（）。A79,46,56,38,40,80C84,79,56,46,40,38B84,79,56,38,40,46D84,56,79,40,46,38219.设有一组的关键字为19,14,23,1,68,20,84,27,55,11,10,79，用链

6、地址法构造哈希表，哈希函数为 H( key )=key mod 13，则哈希地址为 1 的链中有（ ）个。A4B3C2D120.下面关于求关键路径的说法不正确的是（A求关键路径是以拓扑排序为基础的）。B一个C一个的最早开始时间与以该的最迟开始时间为以该为尾的弧的活动最早开始时间相同为尾的弧的活动最迟开始时间与该活动的持续时间的差D关键活动一于关键路径上二、综合应用题 （每题 6 分，共 30 分）21.依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树：(1) 试画出生成之后的二叉排序树;(2) 假定每个元素的查找概率相等，试计算该

7、二叉排序树的平均查找长度。22.有 5 个元素，其入栈次序为 A、B、C、D、E。请问在各种可能的出栈序列中，第一个出栈元素为C 且第二个出栈元素为 D 的出栈序列有哪几个。323.给出一组关键字：29，18，25，47，58，12，51，10，先建成一个大顶堆， 然后从堆顶取下一个元素，再将堆调整成大顶堆，这时的关键字序列是什么？24.考虑下图：根据普利姆(Prim)算法求它的最小生成树。25.有一份电文中共使用 8 个字符：a,b,c,d,e,f,g,h。它们的出现频率依次为15,3,14,2,6,9,16,17，请画出对应的赫夫曼树（按左子树根结点的权值小于等于右子树根结点的权值的次序构

8、造），并求出每个字符的赫夫曼编码。4三、程序阅读题（2*5 分=10 分）26. 阅读下面的算法：LinkList mynote(LinkList L)/L 是不结点的单链表的头指针if (L && L->next)q = L;L = L -> next; p = L;While ( p -> next) p = p -> next; p -> next = q;q -> next = NULL;return L;如果链表表示的线性表为（a1, a2, , an），写出算法执行后的返回值所表示的线性表。27. 简述以下算法的功能（栈和队列的元

9、素类型均为void algo2(Queue &Q)Stack S; int d; InitStack (S);while (!QueueEmpty(Q)DeQueue(Q, d); Push(S, d);while (!StackEmpty(S)Pop(S, d); EnQueue(Q, d);int）。5四、算法填空题（5 分）28. 完善下列折半排序算法。说明：struct node 为已定义的结构体类型，其中包含 key 成员，是该结构体的关键字。以下函数中，形参r 为传入的结构体数组，需要根据关键字对该数组进行从小到大排序；形参n 为数组的大小。void binasort（struct noderMAXSIZE，int n）for（i=2；i<=n；i+） r0=ri；low=1；high=i-1； while（low<=high）mid=（1）；if（r0.key<rmid.key） high=（2）；else low=（3）_；for（j=i-1；j>=low；j- -）_（4）；rlow=（5）；五、算法设计题（共 15 分，第 1 题 7 分，第 2 题 8 分）29. 有一个结点的单链表中（不同结点的数据域的值可能相同），其头指针为 head，试设计一个算法，删除数据域为 x 的所有结点，并返回删除的结