《2017年秋试卷号1252数据结构本》由会员分享，可在线阅读，更多相关《2017年秋试卷号1252数据结构本（8页珍藏版）》请在金锄头文库上搜索。
1、试卷代号:1252座位号E口 国家开放大学(中央广播电视大学)2017年春季学期“开放本科“期末考试 数据结构(本)试题 2017年6月 E 四 EJ 一、单项选择题(每小题3分，共30分) 1.设有一个长度为26的顺序表，要插入一个元素，并使它成为新表的第6个元素，需移 动元素的个数为(。 A.21 B. 22 C. 20 D.19 2.头指针为head的带头结点的单向循环链表，p指向尾结点，要使该链表成为不带头结 点的单向循环链表，可执行head= head-next;和(。 A. p= head-next C. head-next=p-next B. head-next=p D. p-
2、next = head ; 3.元素111，113，115，117按顺序依次进拢，则该校的不可能输出序列是() (进找出 钱可以交替进行)。 A.117,115 ,113,111 C.117,115 ,111 ,113 B.111,113 ,115 ,117 D.113,111 ,117 ,115 4.设有一个20阶的对称矩阵A(第一个元素为al.l)，采用压缩存储的方式，将其下三角 部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵元素a6.2在一维数组B 中的下标是()。 A. 21 C. 28 B.17 D.23 723 5.设有串pl=“ ABADF“ ,P2 =“ ABA
3、FD“ ,P3 =“ ABADF A“ ,P4 =“ ABAF“ ，以下四个串 中最大的是()。 A. p3 C. pl B. p2 D. p4 6.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为()。 A.2i十l C. 2i B.2i-l D.2i十2 7.如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶 点序列为。 A. abecdf C. aebcfd 图1 B. aecbdf D. aedfcb 8.线性表以(方式存储，能进行折半查找。 A.链接B.顺序 C.关键字有序的顺序D.二叉树 9.一棵具有38个结点的完全二叉树，最后一层有()个
4、结点。 724 A.7 C.6 B.5 D.8 10.下图的拓扑序列是()。 A.52346 C.S6234 图2 B.23645 D.2 3 5 6 4 二、填空题(每小题2分，共24分) 11.结构中的数据元素存在多对多的关系称为结构。 12.n个元素进行冒泡法排序，第j趟冒泡要进行一一一一次元素间的比较。 13.中序遍历树可得到一个有序序列。 14.待排序的序列为8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两趟选择后.结果 序列为 15.广义表(a，b)，d，e，(i，j)，k)的长度是 16.广义表的仇，a，(a, b) ,d,e, (i,j) ，k)深度是一一一一。 1
5、7.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行10列的稀疏矩阵A共有 95个零元素，其相应的三元组表共有一一一一个元素。 18.在对一组记录(50，49，97，22，16，73，65，47，88)进行直接插入排序时，当把第7个记 录65插入到有序表时，为寻找插入位置需比较次。 19.一棵有5个叶结点的哈夫曼树，该树中总共有一一一一一个结点。 20.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有一一一一-个结点。 (根所在结点为第1层)。 21.设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为一一一。 22.有以下程序段 char aJ = “English“
6、; char铸p=a;intn=O; while(铸p!0)n+ ;p+;结果中，n的值是一一一一一。 725 三、综合题(每小题中每问5分，共30分) 23.有一个长度为11的有序表(1，2，11，15，24，28，30，56，69，70，80)，元素的下标依次为 1， 2，3，11，按折半查找对该表进行查找。 0)画出对上述查找表进行折半查找所对应的判定树。 (2)说出成功查找到元素56，需要依次经过与哪些元素的比较? (3)说出不成功查找元素72，需要进行元素比较的次数? 24. Cl)一组记录的关键字序列为(57，90.67，50.51.56)，利用堆排序(堆顶元素是最小元 素)的方法
7、建立初始堆(要求以完全二叉树描述)。 (2)对关键宇序列(56，51.71，54，46，106)利用快速排序，以第一个关键字为分割元素，给 出经过一次划分后的结果。 (3)一组记录的关键字序列为(60，47，80，57，39，41，46，30)，利用归并排序的方法，分别给 出口，1)归并、(2，2)归井、(4，4)归并的结果序列。 |得分|评卷人| | 四、程序填空题(每空2分，共16分) 25.设线性表为06，20，26，24)，以不带头结点的单向链表存储，链表头指针为head，以下 程序的功能是输出链表中各结点中的数据域datao struct node intdata; struct n
8、ode养next; typedef struct node NODE; * define NULL 0 void mainO NODE提head，铃p; p=head; /铃p为工作指针铃/ 726 do printf(“%dn“, (1) (2) while( (3) 26.以下函数为直接选择排序算法，对al a2，an中的记录进行直接选择排序，完 成程序中的空格 typedef struct int key; NODE; void selsort(NODE a口，intn) -K +L n NODE temp; for(i=l;i p品 p = ,tPA .、， =d叮L 9白 “/E 飞、 (3)p! =NULL 26. Cl)n-1 (2)n (3)k=j (4)aiJ=akJ (5)akJtemp 730
