资源描述
2017 年硕士研究生招生考试试题（A 卷）科目代码及名称：831 数据结构 适用专业：081201 计算机系统结构081202 计算机软件与理论第 1 页，共 6 页（请考生在答题纸上答题，在此试题纸上答题无效）一、 单项选择题（每小题 3 分，共 45 分）1. 线性表中的每一个元素都有一个前驱和后继元素。这个断言是（ ） 。A. 正确的 B. 错误的2. 线性表的链接实现有利于（ ）运算。A. 插入 B. 读表元 C. 查找 D. 定位3. 在一个带有头结点的单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行（ ） 。A. HLp; p-nextHL; B. p-nextHL; HLp;C. p-next=Hl; pHL; D. p-nextHL-next; HL-nextp;4. 字符 A、B、C、D 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（ ）个不同的字符串？A. 15 B. 14 C. 16 D. 215. 采用链结构存储线性表时，其结点地址（ ） 。A. 必须是连续的 B. 连续不连续都可以C. 部分地址必须是连续的 D. 必须是不连续的6. 队列的删除操作是在（ ）进行。A. 队首 B. 队尾 C. 队前 D. 对后7. 当利用大小为 N 的数组顺序存储一个栈时，假定用 top=N 表示栈空，则退栈时，用（ ）语句修改 top 指针。A. top+; B. top=0; C. top-; D. top=N;8. 二叉树的第 i 层上最多含有结点数为（ ） 。A. 2i B. 2i-1-1 C. 2i-1 D. 2i+1-19. 完全二叉树中，若一个结点没有左孩子，则它必是叶子。这个断言是（ ） 。A. 正确的 B. 错误的10. 不使用递归也可实现二叉树的先序、中序和后序遍历。这个断言是（ ） 。A. 正确的 B. 错误的11. 对于下图的 AOE 网中，计算顶点 4 所表示的事件最早发生时间 ve(4)是（ ） 。2017 年硕士研究生招生考试试题（A 卷）科目代码及名称：831 数据结构 适用专业：081201 计算机系统结构081202 计算机软件与理论第 2 页，共 6 页A. 6 B. 11 C. 12 D. 1312. 采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。这个断言是（ ） 。A. 正确的 B. 错误的13. 已知数据序列为34，76 ，45，18，26，54，92，65，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ） 。说明：如果树只有一个结点，深度为 1。A. 4 B. 5 C. 6 D. 714. 有一棵平衡二叉树，它的广义表表示为 40(30, 130(60, 150)，在它中插入关键字 50 后，重新调整得到一棵新平衡二叉树，在新平衡二叉树中，关键字 60 所在结点的左、右子结点的关键字分别是（ ） 。A. 30, 130 B. 30, 150 C. 40, 130 D. 50, 13015. 对不稳定的排序算法，不论采用何种描述方式，总能举出一个说明它不稳定的实例来。这个断言是（ ） 。A. 正确的 B. 错误的二、 简答题（每个小问 5 分，共 35 分）1. 已知二叉树的后序遍历序列为 41253，中序遍历序列为 45213，则它的先序遍历序列？2. 以3，7，8，2，6，10，14为，权值构造一棵 Huffman 树，这棵 Huffman 树的 WPL？3. 对于下图，按照 Kruskal 算法构造它的一棵最小生成树，拭写出在最小生成树中依次得到的各条边。4. 对一组关键字序列20， 66，34，98，15，53，21， 58，2，10，44，30 ，散列函数为 H(key) = key % 13，表长为 13。用线性探测法（F(i)=i）处理冲突，计算在等概率情况下查找成功的平均查找长度和查找不成功的平均查找长度。=2017 年硕士研究生招生考试试题（A 卷）科目代码及名称：831 数据结构 适用专业：081201 计算机系统结构081202 计算机软件与理论第 3 页，共 6 页=5. 给定关键字序列72，87 ，61，23，94，16，5，58，建小根堆。画出小根堆。6. 设一组初始记录关键字序列5，2，6，3，8 ，以第一个记录关键字 5 为基准进行一趟快速排序的结果？三、 算法填空题（每空 2 分，共 30 分）1. 本题针对线性表的链式存储结构，完成相应的算法。typedef int ElementType;typedef struct NodeElementType data;struct Node *next;Node, *LinkList;void outputList (LinkList L) /*输出带头结点的单链表*/Node *p;（1） ; /*使 p 指向单链表的第 1 个结点*/while(p!=NULL)printf(p-data);（2） ; /*p 后移*/void insertHead(LinkList L, ElementType x)/*L 指向头结点。在单链表中插入一个结点。头插法*/*开辟空间*/（3） ;s-data=x;/*链接*/（4） ;（5） ;2. 下面是三元组表的存储结构及相应的算法，完成相应的算法。typedef structint row, col; /*非零元素的行下标和列下标*/ElementType value; /*非零元素的值*/Triple;2017 年硕士研究生招生考试试题（A 卷）科目代码及名称：831 数据结构 适用专业：081201 计算机系统结构081202 计算机软件与理论第 4 页，共 6 页#define MAXSIZE 1000/*非零元素个数最多为 1000*/typedef struct/*非零元素的三元组表 */Triple dataMAXSIZE+1; /*data0不用*/int m, n, number; /*矩阵的行数 m, 列数 n 和非零元素个数 number*/TSMatrix;/*采用“列序递增“ 法, 将矩阵 A 转置为矩阵 B*/void transposeTSMatrix(TSMatrix *A, （6） )int col, t, p;B-m = A-n;B-n = A-m;B-number = A-number;if(A-number0)p=0;/*记录下标*/for(col=1; coldatat.col=col)（10） ;B-datap.row = A-datat.col;B-datap.col = A-datat.row;B-datap.value = A-datat.value;3. 下面是图的邻接表存储结构及相应的算法，完成相应的算法。#define MAXVEX 100 /*最大顶点数*/typedef char VertexType;struct ALGraphStruct;typedef struct ALGraphStruct *ALGraph;typedef struct EdgeNodeint adjVertex; /*该边所指的顶点的位置*/int weight; /*边的权*/struct EdgeNode *nextEdge; /*指向下一条边的指针*/EdgeNode;2017 年硕士研究生招生考试试题（A 卷）科目代码及名称：831 数据结构 适用专业：081201 计算机系统结构081202 计算机软件与理论第 5 页，共 6 页typedef struct VNodeVertexType data; /*顶点信息 */EdgeNode *firstEdge; /*指向第一条依附该顶点的边的弧指针*/VNode;struct ALGraphStructVNode vexsMAXVEX;int vertexNum,edgeNum; /*图的当前顶点数和弧数*/;/*在无向网中插入一条边。插入的边结点作为边链表的第 1 个结点。如果待插入的边已存在, 存储小权值。*/void addEdge(ALGraph g, VertexType v1, VertexType v2, int w)EdgeNode *s,*t;int i=locateVertex(g, v1); /*找顶点 v1 的位置*/int j=locateVertex(g, v2); /*找顶点 v1 的位置*/if(i=-1 | j=-1)（11） ;s=findEdge(g, i, j);if(s!=NULL)t=findEdge(g, j, i);if(s-weightw)s-weight=w;（12） ;return;s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjVertex=j;s-weight=w;（13） ;g-vexsi.firstEdge =s;t=(EdgeNode*)malloc(sizeof(EdgeNode);t-adjVertex=i;t-weight=w;（14） ;g-vexsj.firstEdge =t;（15） ;2017 年硕士研究生招生考试试题（A 卷）科目代码及名称：831 数据结构 适用专业：081201 计算机系统结构081202 计算机软件与理论第 6 页，共 6 页四、 算法设计题（共 40 分）1. 按照给定的函数原型完成冒泡排序。 （10 分）/*冒泡排序（升序）*/void bubbleSort(int r, int n);2. 下面是顺序表的结构，设计一个高效算法，在顺序表中删除所有元素值为 x 的元素，要求空间复杂度为 O(1)。假设顺序表的数据元素类型为整型。 （10 分）typedef int ElementType;typedef structElementType *array; /*存放元素的数组*/int length; /*已经有多少元素*/int capacity; /*容量*/SeqList;3. 下面是哈夫曼树的存储结构，按照给定的函数原型完成求哈夫曼编码算法。 （20 分）#define N 20 /*叶子结点数 */typedef structint weight; /*结点的权值 */int parent; /*双亲的下标 */int left; /*左孩子结点的下标 */int right; /*右孩子结点的下标 */HTNode, HTree;/*从叶子结点到根, 逆向求每个叶子结点对应的哈夫曼编码*/*第 1 个参数存储哈夫曼树，第 2 个参数存储哈夫曼编码，第 3 个参数是叶子数*/void createHuffmanCode(HTree ht, char *hc, int n);
展开阅读全文