精选解放军电子工程学院攻读硕士学位研究生入学考试样卷计算机基础-数据结构

1、解放军电子工程学院*年攻读硕士学位研究生入学考试试卷考试科目：?数据结构? 75分一、选择题：每题2分，共20分组成数据的根本单位是 。(A) 数据项 (B) 数据类型 ( C) 数据元素 (D)数据变量设输入序列为1、2、3、4、5、6，那么通过栈的作用后可以得到的输出序列为 B 。(A) 5，3，4，6，1，2(B) 3，2，5，6，4，1(C) 3，1，2，5，4，6(D) 1，5，4，6，2，3 在二叉排序树中插入一个关键字值的平均时间复杂度为 。(A) O(n) (B) O(log2n) (C) O(nlog2n) (D) O(n2)设某棵二叉树中只有度数为0和度数为2的结点，且度数

2、为0的结点数为n，那么这棵二叉中共有 个结点。(A) 2n(B) n+l(C) 2n-1(D) 2n+l 在以下排序算法中稳定的排序算法为 。 (A) 直接插入排序 (B) shell排序 (C) 堆排序 (D) 快速排序设无向图G中有n个顶点e条边，那么其对应的邻接表中的表头结点和表结点的个数分别为 。(A) n，e(B) e，n(C) 2n，e(D) n，2e假设数组S1.n作为两个栈S1和S2的存储空间，对任何一个栈，只有当1n全满时才不能进行进栈操作。为这两个栈分配空间的最正确方案是( )。 (A) S1的栈底位置为0，S2的栈底位置为n+l (B) S1的栈底位置为0，S2的栈底位置

3、为n/2 (C) S1的栈底位置为1，S2的栈底位置为n (D) S1的栈底位置为1，S2的栈底位置为l下面关于线性表的表达中，错误的选项是哪一个？ (A)线性表采用顺序存储，必须占用一片连续的存储单元。(B)线性表采用顺序存储，便于进行插入和删除操作。(C)线性表采用链接存储，不必占用一片连续的存储单元。(D)线性表采用链接存储，便于插入和删除操作。假设以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单元，基地址为10，那么LOC5，5= 。(A) 808 (B) 818 (C) 1010 (D) 1020对稀疏矩阵进行压缩存储目的是 。(A) 便于进行

4、矩阵运算 (B) 便于输入和输出 (C) 节省存储空间 (D) 降低运算的时间复杂度二、填空题：每空1分，共10分1.对算法从两方面进行度量，分别称为 分析和 分析。2. 线性表是n个元素的 。3. 线性表的存储结构有 和 。当线性表的元素总数根本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。4. 队列已满，但队列空间未被充分利用，此现象称 。5. 二叉树第i层上最多有 个结点。6. 在AVL树中，由于在A结点的右孩子的右子树上插入结点，使A结点的平衡因子由-1变为-2，使其失去平衡，应采用 型平衡旋转。7. 堆排序的时间复杂度为 。三、简答题：20

5、分1求以下程序段的时间复杂度：4分1i=s=0;while(sn) i+;s+=i; 2fact(int n) if(ndatadata)if(s=0) hc=s=ha; else s-next=ha; s=ha;ha=ha-next; else if(s=0) hc=s=hb; else s-next=hb; s=hb;hb=hb-next; if(ha=0) s-next=hb; else s-next=ha;2一棵二叉树以二叉链表的形式存储，请编写一算法判断该二叉树是否为二叉排序树。8分答案：int last=0,flag=1; int Is_BSTree(Bitree T)/判断二叉树

6、T是否二叉排序树,是那么返回1,否那么返回0if(T-lchild&flag) Is_BSTree(T-lchild);if(T-datadata;if(T-rchild&flag) Is_BSTree(T-rchild);return flag;/Is_BSTree 3.设计一个算法，判断一个算术表达式中的括号(包括：、)是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。9分题目分析表达式中的括号有以下三对：、，使用栈，当为左括号时入栈，右括号时，假设栈顶是其对应的左括号，那么退栈，假设不是其对应的左括号，那么结论为括号不配对。当表达式

7、结束，假设栈为空，那么结论表达式括号配对，否那么，结论表达式括号不配对。int Match(LinkedList la)/算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确配对char s; /s为字符栈，容量足够大p=la-link; /p为工作指针，指向待处理结点StackInit(s); /初始化栈s while (p!=la) /循环到头结点为止 switch (p-ch) case (:push(s,p-ch); break; case ):if(StackEmpty(s)|StackGetTop(s)!=()printf(“括号不配对n); return(0); else pop(s);break;case :push(s,p-ch); break; case : if(StackEmpty(s)|StackGetTop(s)!=)printf(“括号不配对n); return(0); else pop(s);break;case :push(s,p-ch); break; case : if(StackEmpty(s)|StackGetTop(s)!=)printf(“括号不配对n); return(0); else