试卷代号：1252 座位号■■ 国家开放大学（中央广播电视大学）2015年春季学期“开放本科”期末考试 数据结构（本）试题 2015年7月 题 号 二 三 四 总分 分 数 得 分 评卷人 一、单项选择题（每小题2分，共30分） 1,下面关于线性表的叙述中，错误的是()。 A.线性表采用顺序存储，必须占用一片连续的存储空间 B.线性表采用顺序存储，进行插人和删除操作，不需要进行数据元素间的移动 C.线性表采用链式存储，不必占用连续的存储空间 D.线性表采用链式存储，进行插入删除操作，不需要移动元素 2,设有一个长度为28的顺序表，要在第12个元素之前插入一个元素（也就是插人元素 作为新表的第12个元素)，则移动元素个数为()。 A.12 B.17 C.13 D.11 3.元素2,4,6,8按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交替 进行)。 A.8,6,4,2 B.2,4,6,8 C.4,2,8,6 D.8,6,2,4 4.对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值，则执行()。 A.e=top->next;top->data=e; B.e=top->>data;top=top->>next; C.top=top->next;e=top->>data; D.top=top->next;e=data; 843
试卷代号 :1252 座位号rn 国家开放大学(中央广播电视大学)2015 年春季学期"开放本科"期末考试 数据结构{本) 试题 口二 四仄言 一」 一、单项选择题{每小题 分，共 30 分} 1 .下面关于线性表的叙述中，错误的是( )。 A. 线性表采用顺序存储，必须占用一片连续的存储空间 2015 B. 线性表采用顺序存储，进行插入和删除操作，不需要进行数据元素间的移动 c.线性表采用链式存储，不必占用连续的存储空间 D. 线性表采用链式存储，进行插入删除操作，不需要移动元素 2 .设有一个长度为 28 的顺序表，要在第 12 个元素之前插入一个元素(也就是插入元素 作为新表的第 12 个元素) ，则移动元素个数为( )。 A.12 B.17 C. 13 D.11 3. 元素 按顺序依次进枝，则该校的不可能输出序列是( )(进找出战可以交替 进行)。 A. 8 , 6 , 4, 2 C. 4 , 2, 8 ,6 B. 2 , 4 , 6 , 8 D. 8 , 6, 2 , 4 4. 对一个楼顶指针为 top 的链战进行出找操作，用变量 保存钱顶元素的值，则执行( )。 A. e= top->next; top->data=e; C. top=top->next; e=top->data; B. e=top->data; top=top->next; D. top=top->next; e=data; 843
5.在一个尾指针为rear的不带头结点的单循环链表中，插人一个s所指的结点，并作为 第一个结点，可执行()。 A.rear-next=s;s-next=rear-next B.rear→next=s→next; C.rear=s-next D.s-next=rear-next rear-next=s; 6.设有一个28阶的对称矩阵A(矩阵的第一个元素为1,1)，采用压缩存储的方式，将其 下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第40号元素对 应于矩阵中的元素是()。 A.81o.8 B.ag. C.ap.5 D.a8,5 7.数组a经初始化char a[]=“English”；a[1]中存放的是()。 A.字符n B.字符E C."n" D."E" 8.程序段char a[]=“English'”;char*p=a;intn=0;while(*p！=\0'){n十+；P+十；》 结果中，P指向() A.字符h B.a C.字符串的结束符 D.7 9.在一棵二叉树中，编号为17的结点的双亲结点的的顺序编号为()。 A.34 B.7 C.9 D.8 10.设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有20 个指针域为空。则该树共有( )个非叶子结点 A.21 B.22 C.9 D.10 844
5. 在一个尾指针为 rear 的不带头结点的单循环链表中，插入一个 所指的结点，并作为 第一个结点，可执行( )。 A. rear-next= s; ~next=rear- "next B. rear-next= s• next; C. rear=s• next O. '-next = rear-next rear-next = s; 6. 设有一个 28 阶的对称矩阵 A( 矩阵的第一个元素为 al l) ，采用压缩存储的方式，将其 下三角部分以行序为主序存储到一维数组 中(数组下标从 开始) ，则数组中第 40 号元素对 应于矩阵中的元素是( A. alO, 8 B. 句， c.句， O. 句， 7. 数组 经初始化 char a[ ] = "English"; a[l] 中存放的是( )。 A. 字符 B. 字符 C."n" O. "E" 8. 程序段 char a[ ] = "English"; char p=a; int n=O; while( p! \0') { 十+; P++;} 结果中， 指向( ) A. 字符 Ra C. 字符串的结束符 0.7 趴在一棵二叉树中，编号为 17 的结点的双亲结点的的顺序编号为( )。 A.34 B.7 C. 9 0.8 10. 设→棵采用链式存储的二叉树，除叶结点外每个结点度数都为 ，该树结点中共有 20 个指针域为空。则该树共有( )个非叶子结点 A.21 B.22 C. 9 0.10 844
11.已知如图1所示的一个图，若从顶点V0出发，按深度优先法进行遍历，则可能得到的 一种顶点序列为()。 V 图1 A.VeV V2 V Ve Vs V:Vs V7 B.VoV V2 VV Vs Va Vs V C.VoV V2VVsV:VsVs Vz D.VoV V:Vs V:V2 V Vs Vs 12.对( )进行中序遍历，可以使遍历所得到的序列是有序序列。 A.完全二叉树 B.二叉排序树 C满二叉树排 D.哈夫曼树 13.有一个长度为7的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的 平均比较次数为()。 A.17/7 B.18/7 C.21/7 D.20/7 14.排序方法中，从未排序序列中挑选元素，并将其依次放人已排序序列（初始为空）的一 端的方法，称为( )排序。 A.堆 B.冒泡 C.选择 D.快速 15.一组记录的关键字序列为(12,45,22,4,6,50)，利用快速排序，以第一个关键字为分割 元素，经过一次划分后结果为()。 A.6,4,12,45,22,50 B.6,4,12,22,45,50 C.6,4,12,50,22,45 D.4,6,12,22,45,50 845
1.已知如图 所示的一个图，若从顶点 VO 出发，按深度优先法进行遍历，则可能得到的 →种顶点序列为( )。 A. VCV)V2V4VSV5V3V6V7 C. VOV)V2V4VSV3VSV6V7 〉〈三〉 B. VOV)V2V4VSVSV3V6V7 D. VOV)V3V6V7V2V4V5VS 12. 对( )进行中序遍历，可以使遍历所得到的序列是有序序列。 A. 完全二叉树 B. 二叉排序树 c.满二叉树排 D.晗夫曼树 13. 有一个长度为 的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的 平均比较次数为( )。 A. 17/7 B. 18/7 C.21/7 D.20/7 14. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(初始为空)的一 端的方法，称为( )排序。 A. B. 冒泡 c.选择 D. 快速 15. 一组记录的关键字序列为(1 ，屿， 22 50) ，利用快速排序，以第一个关键字为分割 元素，经过一次划分后结果为( )。 A.6 , 4 , 12 , 45 , 22 , 50 C.6 , 4 , 12 , 50 , 22 , 45 B.6 , 4 , 12 , 22 , 45 , 50 D.4 , 6 , 12 , 22 , 45 , 50 845
得分 评卷人 二、填空题（每小题2分，共24分） 16.结构中的数据元素存在一对一的关系称为 结构。 17.向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行 和h=s;操作。（结点的指针域为next) 18.广义表的(a,a,b,d,e,((i,j),k))表头是 19.广义表的((a,c),d,(e,i,j,k))表尾是 20.设顺序队列的类型为typedef struct {ElemType data[MaxSise]; int front,rear; )Squeue; Squeue sq; $q为指向顺序队列的指针变量，要进行新元素x的人队操作，按教课书约定，可用语句 sq->data[sq->rear]=x; 21.对16个元素的序列用冒泡排法进行排序，共需要进行」 趟冒泡。 22.在对一组记录(50,34,92,19,11,68,56,41,79)进行直接插入排序（由小到大排序）， 当把第8个记录41插人到有序表时，为寻找插人位置需比较 次。 23.数据的 在计算机中的表示称为物理结构。 24.循环队列用a[0],…,a[5]的一维数组存放队列元素，（采用少用一个元素的模式），设 front和rear分别为队头和队尾指针，且front和rear的值分别为3和0，当前队列中的元素个 数是 25.设已有m个元素有序，在未排好序的序列中挑选第m十1个元素，并且只经过一次元 素的交换就使第m十1个元素排序到位，该方法是 e 26.对稀疏矩阵进行压缩存储，可采用三元组表，一个6行7列的稀疏矩阵A相应的三元 组表共有8个元素，则矩阵A共有 个零元素。 27.在双向链表中，要删除p所指的结点，可以先用语句(p>next)->prior=(p>prior);然后 再用语句(p>prior))->next= 846
二、填空题{每小题 分，共 24 分) 16. 结构中的数据元素存在一对一的关系称为一一一一一结构。 17. 向→个钱顶指针为 的链战中插入一个 所指结点时，可执行 h=s; 操作。(结点的指针域为 next) 18. 广义表的( a , a , b , d , e ,( (i ,j) k)) 表头是 19. 广义表的( (a , c) , d ,( e ,i ,j k)) 表尾是 20. 设顺序队列的类型为 typedef struct { ElemType data[MaxSise]; int front , rear; }Squeue; Squeue sq; sq 为指向顺序队列的指针变量，要进行新元素 的人队操作，按教课书约定，可用语句 sq->data[sq->rear] = x; 1.对 16 个元素的序列用冒泡排法进行排序，共需要进行 趟冒泡。 22. 在对一组记录 (50 34 9Z 19 11 68 56 41 79) 进行直接插入排序(由小到大排序) , 当把第 个记录 41 插入到有序表时，为寻找插入位置需比较-一一-一次。 23. 数据的 在计算机中的表示称为物理结构。 24. 循环队列用 a[O] ，…， a[ 町的一维数组存放队列元素， (采用少用一个元素的模式) ，设 front rear 分别为队头和队尾指针，且 front rear 的值分别为 ，当前队列中的元素个 数是 25. 设已有 个元素有序，在未排好序的序列中挑选第 m+1 个元素，并且只经过一次元 素的交换就使第 个元素排序到位，该方法是 26. 对稀疏矩阵进行压缩存储，可采用三元组表，一个 列的稀疏矩阵 相应的三元 组表共有 个元素，则矩阵 共有 个零元素。 27. 在双向链表中，要删除 所指的结点，可以先用语句(p->next)- > prior = (p- >prior); 然后 再用语句(p->prior)->next= 846
得 分 评卷人 三、综合题（每小题15分，共30分） 28.对给定的数列b={6,15,3,7,19,8,5,17,4} (1)依次取b中各数据，构造一棵二叉排序树。 (2)给出按中序遍历该二叉排序树的序列。 (3)给出按后序遍历二叉排序树的序列。 (4)画出在二叉树中副除结点3后的树结构。 29.(1)以4,5,6,13,11,12作为叶结点的权，构造-一棵哈夫曼树。 (2)给出相应权重值叶结点的哈夫曼编码。 (3)一棵哈夫曼树有个叶结点，该树共有多少个结点？简述理由？ (4)给出对上述哈夫曼树中序遍历的序列。 得 分 评卷人 四、程序填空题（每空2分，共16分）】 30.职工信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从1到n,以a[0]作 为辅助工作单元。现要以职工的工资号um为关键字进行排序，采用折半插入排序的算法， 以下程序是要把a[i门插人到已经有序的序列a[1],…a[i-1]中，(i=2,3,4,…,n)。 typedef struct char sex; int num; }NODE; void binsort (NODE a[]int n) int x,i,j,s,k,m; for(i=2;i<=(1) i++) 847
三、综合题{每小题 15 分，共 30 分) 28. 对给定的数列 b={ 15 汀， 19 17 4} (1)依次取 中各数据，构造一棵二叉排序树。 (2) 给出按中序遍历该二叉排序树的序列。 (3) 给出按后序遍历二叉排序树的序列。 (4) 画出在二叉树中删除结点 后的树结构。 29. (1)以 13 11 12 作为叶结点的权，构造一棵哈夫曼树。 (2) 给出相应权重值叶结点的晗夫曼编码。 (3) 一棵哈夫曼树有 个叶结点，该树共有多少个结点?简述理由? (4) 给出对上述哈夫曼树中序遍历的序列。 |得分|评卷人| | 四、程序填空题{每空 分，共 16 分} 30. 职工信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从 ，以 a[O] 为辅助工作单元。现要以职工的工资号 为关键宇进行排序，采用折半插入排序的算法， 以下程序是要把 a[iJ 插入到已经有序的序列 a[ 刀， "'a[i-lJ 中，( i=2 ，…， n) typedef struct char sex; mt nu口1; }NODE j void binsort (NODE a[ ] ,int n) int x , i,j ,s, k , ru; for (i= 2; i< = (1) ;i++) 847
{a[0]=a[i; x=afi].num; s=1; j=i-1; while (s=j+1:k--) a[k+1]-(5) aG+1]=a[0]: } 3l.设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针 变量，p指向链表中某结点a(设链表中没有结点的数据域与结点a的数据域相同)，写出相关 语句 (1)使该单向链表成为单向循环链表 (2)删去a结点 q=p;x=p->data; while (q->next!NULL)q=q->next; (1) q=p;p=p->>next; while(p->data！=x) (q=P; (2) } (3) 848
a[OJ=a[iJ; x=~ a[i]. num; s =c 1; j = i-l ; while (5=j+l;k- --) a[k+ l] -.o=- (5) a[j lJc=a[OJ; 1.设有一个头指针为 head 的不带头结点单向链表， 是指向链表中结点类型的指针 变量 .p 指向链表中某结点 a( 设链表中没有结点的数据域与结点 的数据域相同) ，写出相关 语句 (1)使该单向链表成为单向循环链表 (2) 删去 结点 q=p; x=p->data; while (q->next! =NULL)q=q->next; (1) q=p; p= p->next; while(p >data! =x) { q=p; (2) (3) 848
试卷代号：1252 国家开放大学（中央广播电视大学）2015年春季学期“开放本科”期末考试 数据结构（本）试题答案及评分标准 (供参考) 2015年7月 一、单项选择题（每小题2分，共30分） 1.B 2.B 3.D 4.B 5.D 6.B 7.A 8.C 9.D 10.C 11.A 12.B 13.A 14.C 15.B 二、填空题（每题2分，共24分） 16.线性 17.s->next=h; 18.a 19.(d(e,i,j,k)) 20.sq->>rear++; 21.15 22.5 23.逻辑结构 24.3 25.选择排序 26.34 27.p->>next; 849
试卷代号 :1252 国家开放大学(中央广播电视大学 )2015 年春季学期"开放本科"期末考试 数据结构(本) 试题答案及评分标准 (供参考) 一、单项选择题{每小题 分，共 30 分) 1. B 6. B 11. A 2. B 7.A 12. B 二、填空题(每题 分，共 24 分) 16. 线性 17. s->next= h; 18. a 19. (d , (e , i ,j , k)) 20. sq->rear+ 十; 21. 15 22.5 23. 逻辑结构 24.3 25. 选择排序 26.34 27. p->next; 3. D 8. C 13.A 4. B 9. D 14. C 5. D 10. C 15. 2015 849
三、综合应用题（每小题15分，共30分） 28.(1)图2(4分) 6 3 15 5 19 8 17 图2 (2)3,4,5,6,7,8,15,17,19 (4分) (3)4,5,3,8,7,17,19,15,6(4分) (4)图3(3分) 6 15 7 19 8 17 图3 850
三、综合应用题{每小题 15 分，共 30 分} 28. (1)图 (4 分) (2) 3 ,4 ,5 ,6 , 7, 15 17 19 (4 分) (3) 4 ,5 ,3 ,8 ,7 ,17 ,19 ,15 ,6 (4 分〉 (4) (3 分〉 ø 850
29.(1)图4(4分) 51 28 23 5 图4 (2)4 0000 (4分) 5 0001 6 001 13 01 11 10 12 11 (3)2n一1个，因为非叶结点数比叶结点数少一个，非叶结点数为n一1，所以共有2n一1 个。 (3分) (4)4,9,5,15,6,28,13,51,11,23,12 (4分)》 四、程序填空题（每空2分，共16分） 30.(1)n (2)(s+j)/2; (3)j-m-1; (4)s=m十1； (5)a[k] 31.(1)q->next=head; (2)p=p->next; (3)q->>next=p->next; 851
29. (1)图 (4 分) (2) 4 0000 (4 分) 5 0001 6 001 13 01 11 10 12 11 (3)2n-1 个，因为非叶结点数比叶结点数少一个，非叶结点数为 n- l，所以共有 2n-1 个。 (3 分) (4) 4 , 9 , 5 , 15 , 6 , 28 , 13 , 51 , 11 , 23 , 12 (4 分) 四、程序填空题{每空 分，共 16 分} 30. (1) n (2) (s+j) /2; (3) j=m-1; (4) s=m ; (5)a[kJ 31. (1 )q->next=head; (2)p= p->next; (3) q-> next = p-> next; 851