2020年硕士研究生招生考试试题
科目代码及名称：826数据结构 适用专业：081201计算机系统结构
081202计算机软件与理论 （请考生在答题纸上答题，在此试题纸上答题无效）
一、 单项选择题（共10小题，每小题4分，共40分） 1. 在数据结构中，与所使用的计算机无关的是数据的（ ）。 A. 逻辑结构 B. 存储结构 D. 物理结构 C. 逻辑结构和存储结构 2. 算法的时间复杂度属于一种（ ）。 A. 事前统计的方法 C. 事后统计的方法 B. 事前分析估算的方法 D. 事后分析估算的方法 3. 线性表中的所有元素都有一个前驱元素和后继元素。这个说法是（ ）。 A. 正确的 B. 错误的 4. 链式存储的存储结构所占存储空间（ ） A. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B. 只有一部分，存放结点值 C. 只有一部分，存储表示结点间关系的指针 D. 分两部分，一部分存放结点值，另一部分存放结点所占单元数 5. 经过以下栈运算后，x的值是（ ）。 initStack(s); push(s, a); push(s, b); pop(s, &x); top(s, &x); A. a B. b C. 1 D. 0 6. 数组A中，每个元素的长度为4个字节，行下标i从1到8，列下标j从1到10，从首地址100开始连续存放在存储器内。若该数组按行主序存放，则元素A[8][5]的起始地址为（ ）；若该数组按列主序存放，则元素A[8][5]的起始地址为（ ）。 A. 396，217 B. 396，256 C. 256，396 D. 256，217 7. 若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ ）。 A. 9 B. 11 C. 12 D. 不确定 8. 设有无向连通图G中的边集E={(A, B)，(A, C)，(A, E)，(B, E)，(E, D)，(D, F)，(F, C)}。若从顶点A出发按深度优先搜索进行遍历，则可能得到的一种顶点序列为（ ）。 A. {A, B, E, C, D, F} C. {A, E, B, C, F, D} B. {A, C, F, E, B, D} D. {A, E, D, F, C, B} 第 6页，共 6页
2020年硕士研究生招生考试试题
科目代码及名称：826数据结构 适用专业：081201计算机系统结构
081202计算机软件与理论 9. 对于长度为9的有序顺序表，若采用折半查找法，在等概率情况下查找成功的平均查找长度为（ ）的值除以9。 A. 20 B. 18 C. 25 D. 22
10. 排序算法的稳定性是指（ ）。 A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变 C. 排序算法的性能与待排序元素的数量关系不大 D. 排序算法的性能与待排序元素的数量关系密切 二、 填空题（共5小题，每小题10分，共50分） 1. 请完成下面顺序表的操作。顺序表的类型如下。 typedef struct{ ElementType *array; /*存放元素的数组*/ int length; /*已经有多少元素*/ int capacity; /*容量*/ }SeqList; /*在顺序表的第i个位置插入元素x*/ int insertList(SeqList *L, int i, ElementType x) { if(L->length>=L->capacity){ return 0; } if(i<1 || i>L->length+1){ return 0; } for(k=L->length-1; k>=i-1; k--){ L->array[k+1] = L->array[k]; } ____________; ____________; return 1; } 2. 假设通讯电文中只用到A，B，C，D，E，F六个字母，它们在电文中出现的相对频率分别为：8，3，16，10，5，20。（1）用这些信息构造哈夫曼树；（2）计算该哈夫曼树的带权路径长度。 第 6页，共 6页
2020年硕士研究生招生考试试题
科目代码及名称：826数据结构 适用专业：081201计算机系统结构
081202计算机软件与理论 这棵哈夫曼树有____________个结点；该哈夫曼树的带权路径长度（WPL）：____________。 3. 己知序列{99，5，36，7，22，17，46，12，2，19，25，28，1，92}，用这些序列建小根堆。 按照从上到下，从左到右，小根堆的结点序列是：________________________。 4. 已知序列{13, 2, 16, 3, 8, 28, 4, 10, 5, 6, 7}，请按照下面的快速排序算法，给出该序列作升序排列时前三趟的结果。 第1趟：____________________________________； 第2趟：____________________________________； 第3趟：____________________________________。 typedef int ElementType; int partition(ElementType r[], int low, int high) { int pivot; pivot=r[low]; while(low 第 6页，共 6页
2020年温州大学考研真题826数据结构(2020年)
