数据结构练习题1
2012-3
一、单选题（每题 2 分，共20分） 1.以下数据结构中,( )是线性结构。
A.有向图 B.队列 C.线索二叉树 D.B树
2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行( )语句序列。
A.p=q；p->next=q； B.p->next=q； q->next=p； C.p->next=q->next； p=q； D.q->next=p->next； p->next=q； 3.( )不是队列的基本运算。
A.在队列第i个元素之后插入一个元素 B.从队头删除一个元素 C.判断一个队列是否为空 D.读取队头元素的值
4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串。
A.14 B.5 C.6 D.8
5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。
A． 11 B.35 C. 19 D. 53
6.下列二叉树的前序遍历序列为( )。
A.E,G,F,A,C,D,B B.E,A,G,C,F,B,D C.E,A,C,B,D,G,F D.E,G,A,C,D,F,B
二叉树
7.第6题二叉树的中序遍历序列为( )。
A.A,B,C,D,E,G,F B.E,A,G,C,F,B,D C.E,A,C,B,D,G,F D.B,D,C,A,F,G,E 8.第6题二叉树的层次遍历序列为( )。 A.E,G,F,A,C,D,B B.E,A,C,B,D,G,F
C.E,A,G,C,F,B,D D.E,G,A,C,D,F,B 9.下面关于图的存储的叙述中正确的是( )。
A.用邻接表法存储图,占用的存储空间大小只与图中边数有关，而与结点个数
无关。
B.用邻接表法存储图,占用的存储空间大小与图中边数和结点个数都有关。 C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。 D.用邻接矩阵法存储图,占用的存储空间大小只与图中边数有关，而与结点个数无关。
10.设有关键码序列(q,g,m,z,a,n,p,x,h)，下面( )序列是从该序列出发建成的
堆。
A.a,g,h,m,n,p,q,x,z B.a,g,m,h,q,n,p,x,z C.g,m,q,a,n,p,x,h,z D.h,g,m,p,a,n,q,x,z
二、填空题（每空1分，共26分）
1.数据的物理结构被分为______、______、______和_____四种。
2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为______，在表尾插入元素的时间复杂度为_____。
3.向一个由HS指向的链栈中插入一个结点p时，需要执行的操作是____；删除一个结点时，需要执行的操作是____（假设栈不空而且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩子结点的编号为___，若它有右孩子，则右孩子结点的编号为___，若它有双亲，则双亲结点的编号为___。
5.当向一个大根堆插入一个具有最大值的元素时，需要逐层___调整，直到被调整到____位置为止。
6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为____。
7.表示图的三种常用的存储结构为_____、_____和____。
8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有_____个，散列地址为6的有____个。
9.在归并排序中，进行每趟归并的时间复杂度为___，整个排序过程的时间复杂度为_____，空间复杂度为_____。
10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为____个，最多为____个，其子树数目最少为____，最多为____。
三、简答题（每题6分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3)
2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。
图2
(1){ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }
(2){ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }
3.判断以下序列是否是小根堆? 如果不是, 将它调整为小根堆。
4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12, (3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
四、阅读算法（每题7分，共14分） 1.void AE(Stack& S) {
InitStack(S)； Push(S,3)；
int x=Pop(S)+2*Pop(S)； Push(S,x)；
int i,a[5]={1,5,8,12,15}； for(i=0;i<5;i++) Push(S,2*a[i])； while(!StackEmpty(S)) cout< 试指出算法被调用后得到的输出结果。 2.void ABC (BTNode *BT,int &c1,int &c2) Push(S,4)； { if (BT !=NULL ) { ABC(BT->left,c1,c2); c1++; if(BT->left==NULL&&BT->right==NULL)c2++; ABC(BT->right,c1,c2); } } 试问该函数执行的功能是什么？ 五、填空题（共8分） 向单链表的末尾添加一个元素的算法。 Void InsertRear(LNode*& HL,const ElemType& item) { LNode* newptr； newptr=new Lnode； If ( _____________________ ) { cerr<<\； exit(1)； } _____________________=item； newptr->next=NULL； if (HL==NULL) HL= __________________________ ； else { LNode* P=HL； while (P->next!=NULL) ___________________ ； p->next=newptr； } } 六、编写算法（共8分） 编写从类型为List的线性表L中将第i个元素删除的算法，（假定不需要对i的值进行有效性检查,也不用判别L是否为空表。） void Delete(List& L, int i) 参考答案 一、单选题（每题2分，共20分） 1.B 2.D 3.A 4.B 5.B 6.C 7.A 8.C 9.B 10.B 二、填空题（每空1分，共26分） 1. 顺序 链表 索引 散列 2. O(n) O(1) 3. p->next=HS;HS=p HS=HS->next 4. 2i 2i+1 ?i/2?（或i/2） 5. 向上 根 6. 2.9 7. 邻接矩阵 邻接表 边集数组 8. 1 4 9. O(n) O(nlog2n) O(n) 10. ?m/2?-1 m-1 ?m/2? m 三、简答题（每题6分，共24分） 1. (1) 3 X * Y 2 - / 1 + (2) 2 X Y 3 + * + 2. （1） 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 … 18 … 31 1 2 3 4 5 6 7 8 … 9 图3 （2）见图3所示： 3. (1)不是小根堆。调整为：{12,24,33,65,34,56,48,92,86,70} (2)是小根堆。 4. 普里姆算法从顶点1出发得到最小生成树为： (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20 四、阅读算法（每题7分，共14分） 1.30 24 16 10 2 10 2.该函数的功能是：统计出BT所指向的二叉树的结点总数和叶子总数。 五、算法填空（共8分，每一空2分） newptr==NULL newptr->=data newptr p=p->next 六、编写算法（8分） void Delete(List& L, int i) { for(int j=i-1；j L.list[j]=L.list[j+1]； //第i个元素的下标为i-1 L.size--； 小学少先队组织机构 少先队组织由少先队大队部及各中队组成，其成员包括少先队辅导员、大队长、中队长、小队长、少先队员，为了健全完善我校少先队组织，特制定以下方案： 一、成员的确定 1、大队长由纪律部门、卫生部门、升旗手、鼓号队四个组织各推荐一名优秀学生担任（共四名），该部门就主要由大队长负责部门内的纪律。 2、中、小队长由各班中队公开、公平选举产生，中队长各班一名（共11名），一般由班长担任，也可以根据本班的实际情况另行选举。小队长各班各小组先选举出一名（共8个小组，就8名小队长）然后各班可以根据需要添加小队长几名。 3、在进行班级选举中、小队长时应注意，必须把卫生、纪律部门的检查学生先选举在中、小队长之内，剩余的中、小队长名额由班级其他优秀学生担任。 4、在班级公开、公平选举出中、小队长之后，由班主任老师授予中、小队长标志，大队长由少先队大队部授予大队长标志。 二、成员的职责及任免 1、大、中、小队长属于学校少先队组织，各队长不管是遇见该班的、外班的，不管是否在值勤，只要发现任何人在学校内出现说脏话、乱扔果皮纸屑、追逐打闹、攀爬栏杆、乱写乱画等等一些违纪现象，都可以站出来制止或者报告老师。 2、班主任在各中队要对中、小队长提出具体的责任，如设置管卫生的小队长，管纪律的小队长，管文明礼貌的、管服装整洁的等等，根据你班的需要自行定出若干相应职责，让各位队长清楚自己的职权，有具体可操作的事情去管理，让各位队长成为班主任真正的助手，让学生管理学生。各中队长可以负责全班的任何违纪现象，并负责每天早上检查红领巾与校牌及各小队长标志的佩戴情况。 3、大、中、小队长标志要求各队长必须每天佩戴，以身作则，不得违纪，如有违纪现象，班主任可根据中、小队长的表现撤消该同学中、小队长的职务，另行选举，大队长由纪律、卫生部门及少先队大队部撤消，另行选举。 4、各班中、小队长在管理班级的过程中负责，表现优秀，期末评为少先队部门优秀干部。