《绵职院计科系计应班软件班数据结构期末试卷001b1.doc》由会员分享，可在线阅读，更多相关《绵职院计科系计应班软件班数据结构期末试卷001b1.doc（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构一、选择题：(151分)1. 下面有关链队列的描述正确的是（）。A. 链队列只需要一个指向队头的指针B队尾结点的指针域为空表示队列空C. 入队一个元素实际上是建立一个新的尾结点D出队一个元素实际上是从队尾删除一个结点2. 设栈S和队列Q的初始状态为空，元素1, 2, 3, 4, 5, 6依次通过栈S，一个元素出栈后进入队列Q ，若6个元素出队的顺序是 2, 4， 3, 6, 5, 1 则栈S的容量至少是（）。A. 6 B. 4 C . 3 D. 23. 由3个结点可以构造出（）种不同的二叉树：A. 2 B. 3 C. 4 D. 54. 在下列排序方法中，哪一个是稳定的排序方法（ ）。A
2、直接选择排序 B二分法插入排序C希尔排序 D快速排序5. 对n个记录的序列进行快速排序，所需的辅助存储器空间为( )。A.0(1) B.0(logn) C.0(n) D.0(n2)6. 深度为6的二叉树至多有结点数为( )。A. 11 B65 C. 63 D137. 下面关于串的叙述中，哪一个是不正确的（ ）。A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要的运算D串既是可采用顺序存贮，也可采用链式存贮8. 在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序A都不相同 B. 完全相同C先序和中序相同而后序不同 D. 中序和后序相同而先序不同9. 在堆排序
3、中，当初堆建成后，该堆根的记录必是（ ）。A.文件中的第一个记录B.文件中具有最大（或最小）关键字的记录C.文件中的一个记录D.文件中的最后一个记录10. 下面有向图可以排成不同的拓扑序列，其中正确的序列为（ ）。A、a c b d B、a d b cC、a b c d D、b a d c11. 树形结构中，每个结点（ ）A、无直接前驱 B、可有多个直接前驱C、至多只能有一个直接前驱 D、有三个以上的直接前驱12. 一个深度为4的完全二叉树中序号为13的结点的_。A. 双亲结点序号为6 B. 左孩子结点序号为26C右孩子结点序号为27 D双亲结点序号为713. 对于一个有n个元素的线性表，采用
4、顺序存储结构，若要删除第i个结点，需要移动元素的个数有_个。A.1 B. n C. n-i D.i装 订. 线14. 下面关于数据结构的描述不正确的是_。A数据结构包括的内容是数据的逻辑结构、数据的存储结构、数据运算。B数据的逻辑结构是指数据及其数据的逻辑关系。C数据的存储结构是指数据在计算机中的表示。D数据的运算是指对数据施加的操作。15. 一棵二叉树结点的先根遍历序列为ABCD，中根遍历序列为CBAD，则其后根遍历序列为_。ABCDA B CBDA C BCAD D以上都不对二、填空：(53分+35分)1. 设有二维数组A09，019其中每个元素占两个字节。数组按列优先顺序存贮。第一个元素
5、的存贮地址为100。则元素A6，6的存贮地址为_.2. 对某非空二叉树进行前序、中序遍历时，所得的结果完全相同（即结点序列一致），则这棵二叉树必定是_。3. 对于有n个顶点的连通图，至少有_条边。由此而构成的生成树有_条边。有_条边的无向图为完全图。 4. 设有一个用线性探测法解决冲突得到的Hash表（Hash函数为H(k)=K Mod 11）有一组数（13,25,80,16,17,14,4），则探测元素14的地址值为( )（填入上Hash表中）5. 单链表H的结点在逻辑_（有序/无序），在物理上是_有序/无序）。以下是算法填空装 订. 线6. 下列函数的功能是：对给定的不带头结点的单链表进行
6、逆置，即原线性表(a1, a2,an+1,an) 逆置后变成(an,an-1,a2,a1)。单链表类型定义如下：struct link_node int data; struct link_node *next; struct link_node *revers(struct link_node h) /* h为单链表的头指针，函数返回逆置后的单链表头指针 */ struct link_node *s,*p,*q; qNULL; ph; while(p) s=p-next; _; q=p; p=s; h=q; return(h);7. 下列函数的功能是：实现链式队列的入队操作。其中链式队列的定
7、义如下：typedef struct queue_node int data;struct queue_node *next;QUEUE_NODE;typedet struct queue QUEUE_NODE *front, *tail; QUEUE; void in_like queue(QUEUE q, int key) /* q为链式队列，并且带头结点，key为将要入队的内容 */ QUEUE_NODE *s; s=(QUEUE_NODE*)malloc(sizeof(QUEUE_NODE);s-data=key; s-next=NULL; _;)装 订. 线8. 下列递归函数的功能是
8、：中序输出给定的二叉树结点。其中二叉树中的结点类型定义如下：typedef bin_tree_node int data; bin_tree_node *llink, *rlink; BIN_TREE; void inorder(BIN_TREE *tree) if(tree) _;printf(%d , tree-data);inorder(tree-rlink);三、简答题：(40分)1. 设电文中出现字字母A,B,C,D,每个字母在电文中出现的次数分别是2,7,4,5按哈夫曼编码求A,B,C,D的编码,请作出哈夫曼树.并求WPL.2. 己知如图所示的一棵树，画出其双亲表示法的存储结构图,
9、 并将此树的转化为二叉树。3. 对于如下带全的有向图写出邻结表；并用C语言描述起存储结构。（将其结构填充完整）B卷 第5页 共6 页#define MAXtypedef struct ArcNodeArcNode; /边typedef struct VnodeVnode,AdjlistMAX; /结点typedfe stru int kind /图的种类标志ALGrph /图4. 求图中o点到c的最短路径（描述过程）四、算法设计(15分)装 订. 线带有头指针head的单链表中，存放着n个整数，现从单链表中删除数值为key的结点。编写一个子函数delete，描述该算法；若完成删除，则返回OK否则返回ERROR、其中数据类型和子函数说明用类C语言描述为：#define NULL 0 /* 空指针 */#define OK 1#define ERROR 0typedef struct node /* 结点类型 */int data; /* 数据域 */struct node *next; /* 指针域 */ *list;int key;int delete(list head, int key); /* 子函数说明
