试卷代号：1252 座位号■ 中央广播电视大学2010一2011学年度第二学期“开放本科”期末考试 数据结构（本）试题 2011年7月 题 号 三 四 总分 分 数 得 分 评卷人 一、单项选择题（每小题2分，共30分） 1.( )是性质相同的数据元素的集合，是数据的子集、 A.数据元素 B.数据对象 C.数据结构 D.数据项 2.设链表中的结点是NODE类型的结构体变量，且有NODE p;为了申请一个新结点， 并由P指向该结点，可用以下语句()。 A.p=(NODE *)malloc(sizeof(NODE)); B.p=(*NODE)malloc(sizeof(NODE)); C.p=(NODE )malloc(sizeof(p)); D.p=(NODE *)malloc(sizeof(p)); 3.设顺序存储的线性表长度为，要在第i个元素之前插入一个新元素，按课本的算 法当=( )时，移动元素次数为2。 A.n/2 B.n C.1 D.n-1 4.一个栈的进栈序列是1,2,3,4，则栈的不可能的出栈序列是( )(进出栈操作可以 交替进行)。 A.3,2,4,1 B.1,4,2,3 C.4,3,2,1 D.3,2,1,4 1363
试卷代号 座位号 I --I 中央广播电视大学 1学年度第二学期"开放本科"期末考试 数据结构(本)试题 2011 年7 |题号|一|二|三| |分数[-- [I I 总分 得分|评卷人 一、单项选择题(每小题 2分，共 0分) 1. ( )是性质相同的数据元素的集合，是数据的子集 A. 素B.数据对 c. 据结 数据 2. 设链 是NODE 有NODE 并由 )。 A. p=(NODE malloc{ sizeof(NODE» ; B. p=( 铃NODE)malloc(sizeof(NODE» ; c. p= (NODE )malloc(sizeof(p»; D. p=(NODE malloc(sizeof( p» ; 3. 新 元 课 本 法当 ( )时，移动元素次数为 A. n/2 C. 1 B. n D. n-l 4. 进校序 是1 ，2 ，3 ，4 ) (进出校操作可以 交替进行)。 A. 3 , 2 , 4 , 1 C. 4 ,3 , 2 , 1 B. 1 ,4 ,2 ,3 D. 3 ,2 ,1 ,4 1363
5.设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成， front和rear分别为链队列的头指针和尾指针。设p指向要人队的新结点（该结点已被赋值）， 则入队操作为()。 A.rear->next=p;rear=p; B.rear->next=p;p rear; C.p rear->next;rear=p; D.rear=p;rear->next=p; 6.以下说法不正确的是( )。 A.顺序栈中，栈满时再进行进栈操作称为“上溢” B.顺序栈中，栈空时再作出栈栈操作称为“下溢” C.顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满 D.顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空 7.设有一个20阶的对称矩阵A,采用压缩存储方式，将其下三角部分以行序为主序存储 到一维数组中（矩阵A的第一个元素为a1,数组b的下标从1开始），则矩阵元素aa.5在一维 数组b中的下标是()。 A.30 B.28 C.40 D.33 8.深度为5的完全二叉树第5层上有4个结点，该树一共有()个结点。 A.28 B.30 C.31 D.19 9.已知一个图的所有顶点的度数之和为m,则m一定不可能是()。 A.4 B.8 C.12 D.9 10.以下说法正确的是()。 A.连通图G的生成树中可以包含回路 B.连通图G的生成树可以是不连通的 C.连通图G的生成树一定是唯一的 D.连通图G的生成树一定是连通而不包含回路的 1364
5. 一个数据域data 域next front 和rear 队列 头 指 指针 设p 新结 , 则入队操作为( )。 A. rear- >next=归rear=p; B. rear->next=p; p = rear; c. p = rear->next; l'ear=p; D. rear= p; rear- > next = p; 6. 正确 )。 A. 进行进校 B. c. 队列 经超 队列 间 的 D. 队列 指针 则 队 7. 个20 存储 部分 到一维数组中〈矩阵A的第一个元素为 ll ，数组 b的下标从 开 始 ，则矩阵元素句，5在一维 数组 b中的下标是( )。 A. 30 c. 40 B. 28 D. 33 8. 为5 二叉 第5 有4 个结 )个结点。 A. 28 c. 31 B. 30 D. 19 9. fi 定不 )。 A. 4 B. 8 C. 12 D. 9 10. )。 A. 连通 图G 包含 B. 图G c. 连通 成树 定是 D. 连通 图G 是连通而 不 1364
11.对n个元素进行冒泡排序，通常要进行n一1趟冒泡，在第j趟冒泡中共要进行() 次元素间的比较。 A.j B.j-1 C.n-j D.n-j-1 12.在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是( )。 A.冒泡 B.选择 C.直接插入 D.折半插人 13.如图若从顶点a出发按深度优先搜索法进行遍历，则可能得 到的顶点序列为( )。 A.aebcfd B.abedcf C.acebdf D.acfbde 14.一棵哈夫曼树有n个叶子结点（终端结点），该树总共有 图1 ( )个结点。 A.2n-2 B.2n-1 C.2n D.2n+2 15.数据的( )结构与所使用的计算机无关。 A.逻辑 B.物理 C.存储 D.逻辑与存储 得分 评卷人 二、填空题（每小题2分，共24分） 1.通常可以把一本含有不同章节的书的目录结构抽象成 结构。 2.要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点，若链表中结点 的指针域为next,可执行 和p一>next=s;的操作。 1365
11. 对n 行n-l 进行 ) 次元素间的比较。 A. j c. n-j B. j-l D. n-j-l A. aebcfd B. abedcf c. acebdf D. acfbde 12. 序过 效地 较次数 )。 A. B. 选择 c. D. 13. 按深度 优 索法进 到的顶点序列为( )。 14. 该树 ( )个结点。 A. 2n-2 C. 2n B. 2n-l D. 2n 十2 15. A. 逻辑 C. 〉结构与所使用的计算机无关。 B. D. 逻辑 得分|评卷入 二、填空题(每小题 1. 本含 章节 结构 2. 个单 链 表 插入 链 表 的指针域为 t，可执行和 =川的操作。 1365
3.设有一个非空的链栈，栈顶指针为s,要进行出栈操作，用x保存出栈结点的值，栈结 点的指针域为next,则可执行x=hs一>data; 4.在一个不带头结点的非空链队中，f和r分别为队头和队尾指针，队结点的数据域 为data,指针域为next,若要进行出队操作，并用变量x存放出队元素的数据值，则相关操 作为x=f一>data; 5.循环队列的最大存储空间为MaxSize=8,采用少用一个元素空间以有效的判断栈空 或栈满，若队头指针front=4,则当队尾指针rear= 时，队列为空，当rear= 时，队列有6个元素。 6.稀疏矩阵存储时，采用一个由 、非零元3部分信息组成 的三元组唯一确定矩阵中的一个非零元素。 7.一棵二叉树顺序编号为6的结点（树中各结点的编号与等深度的完全二叉中对应位置 上结点的编号相同)，若它存在右孩子，则右孩子的编号为 8.数据结构中的数据元素存在多对多的关系称为 结构。 9.数据结构中的数据元素存在一对多的关系称为 结构。 10.如图2所示的二叉树，其前序遍历序列为 图2 11.在队列的顺序存储结构中，当插入一个新的队列元素时， 指针的值增1，当删 除一个元素队列时， 指针的值增1。 12.循环队列的引入，目的是为了克服 1366
3. 有一 顶指 为hs 进行 用x 找 结 点的指针域为 t，则可执行 4. 不 带 为 队 数 据 域 a，指针域为 t，若要进行出队操作，并用变量 x存放出队元素的数据值，则相关操 作为 5. 为MaxSize= 素 空 或钱满，若队头指针 4，则当队尾指针 =时，队列为空，当 时，队列有 6个元素。 6. 稀疏矩 元3 的三元组唯一确定矩阵中的一个非零元素。 7. 棵二叉树 为6 对应位 上结点的编号相同) ，若它存在右孩子，则右孩子的编号为 8. 数据 据元 9. 数据 10. 图2 二叉树 遍 历 11. 队列 结构 除一个元素队列时，指针的值增 12. 1366 指针的值增 1，当删
得 分 评卷人 三、综合题（每小题10分，共30分） l.(1)设head1和p1分别是不带头结点的单向链表A的头指针和尾指针，head2和P2分 别是不带头结点的单向链表B的头指针和尾指针，若要把B链表接到A链表之后，得到一个 以head,为头指针的单向循环链表，写出其中两个关键的赋值语句（不用完整程序，结点的链 域为next) (2)单向链表的链域为next,设指针p指向单向链表中的某个结点，指针s指向一个要插 人链表的新结点，现要把s所指结点插人P所指结点之后，某学生采用以下语句： p->next=s;s->next=p->next; 这样做正确吗？若正确则回答正确，若不正确则说明应如何改写。 2.(1)画出对长度为10的有序表进行折半查找的判定树（以序号1,2，…10表示树结 点)。 (2)对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度。 3.（1)利用筛选法，把序列{37,77,62,97,11,27,52,47}建成堆（小根堆），画出相应的完全 二又树。 (2)写出对上述堆所对应的二叉树进行前序遍历得到的序列。 1367
得分|评卷人 三、综合题(每小题 1. (1) 表A 指 针 指 针 head 别是不带头结点的单向链表 B的头指针和尾指针，若要把 B链表接到 A链表之后，得到一个 指针 用 完 域为 (2) 个结 入链表的新结点，现要把 s所指结点插入 p所指结点之后，某学生采用以下语句: 一>next==s; s->next==p->next; 这样做正确吗?若正确则回答正确，若不正确则说明应如何改写 2. (1) 为10 有 序 表 进 号1 ，2 …10 点)。 (2) 3. (1) 筛选法 列{37 ，77 ，62 ，97 ，11 ，27 ，52 ，47} 成堆 小根 二叉树。 (2) 述堆所对 进行前序遍 1367
得 分 评卷人 四、程序填空题（每空2分，共16分） l.以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序，完 成程序中的空格。 typedef struct int key; NODE; void selsort(NODE a[],int n) int i,j,k; NODE temp; for(i=1;i<=(1) ;i++) k=i; for(j=i+1;j<=(2) j++) if(a[j].key<a[k].key)(3) if(i!=k) temp=a[i]; (4)】 68
得分|评卷人 四、程序填空题(每空 2分，共 6分) 1. 接选择排 算法 对a[ ，a[ …a[n] 直接选择排 成程序中的空格。 u. c+t , 4tvdpe kwwF+i'w S'Krvd }NODE; void selsortCNODE ，int n) ··F TK -7 -7 ., - A n4t ..... NhOKe·' ; 十 十 k==i; for(j == 十1;j<=(2) if(a[jJ. key<a[k]. key) (3) if(i! === k) ;j++) temp=a[i] ; (4) (5) 1368
2.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右 指针域分别为left和right,数据域data为字符型，BT指向根结点)。 void Inorder (struct BTreeNode BT) if(BT!=NULL)( (1) (2) 3 1369
2. 程序 格部 指针域分别为 ght，数据域 a为字符型， T指向根结点儿 void Inorder (struct BTreeNode 祷BT) if(BT! =NULL){ (1) (2) (3) 1369
试卷代号：1252 中央广播电视大学2010一2011学年度第二学期“开放本科”期末考试 数据结构（本） 试题答案及评分标准 (供参考) 2011年7月 一、单项选择题（每小题2分，共30分） 1.B 2.A 3.D 4.B 5.A 6.C 7.D 8.D 9.D 10.D 11.C 12.D 13.B 14.B 15.A 二、填空题（每题2分，共24分） 1.树形 2.s->next=p->next; 3.hs=hs->next; 4.f=f->>next; 2 5.4 6.行号 列号 7.13 8.图状 9.树形 10.abdefcg 11.尾头 12.假上溢 三、综合应用题（每小题10分，共30分） 1.(1)p1->>next=head2 ;p2->next=head (2)不对，s->next=p->next;p->next=s; 1370
试卷代号 中央广播电视大学 1学年度第二学期"开放本科"期末考试 数据结构(本)试题答案及评分标准 (供参考) 2011 年7 一、单项选择题(每小题 1. B 2. A 3. D 6.C 7.D 8.D 11.C 12.D 13.B 二、填空题(每题 1. 2. 一>next=== p->next; 3. hs=== hs 一>next; 4. f === 一>next; 5.4 2 6. 行号 7. 13 8. 9. 10. abdefcg 11. 12. 三、综合应用题(每小题 4. B 9. D 14. B 5. A 10. D 15. A 1. (1)Pl == headz; 一>next== head!; (2) == p->next;p一>next==s; 1370
2.(1) 3 9 4 10 (2)ASL=(1x1+2x2+3x4+4x3)/10=29/10 3.(1) 37 11 77 62 37 27 97 27 52 47 77 62 47 97 初始树 堆 (2)11,37,47,97,77,27,62,52 四、程序填空题（每空2分，共16分） 1.(1)n-1 (2)n (3)k=j (4)a[i]=a[k] (5)a[k]=temp 2.(1)Inorder(BT->left) (2)printf(“%c”,BT->data) (3)Inorder(BT->right) 1371
2. (1) 3 (2)ASL= (lxl 十2x2十3x4十4x3)/10 == 29/10 3. (1) / 97 初始树 ITLF (2)11 ,37,47,97 ,77,27,62 ,52 四、程序填空题(每空 1. (l)n-l (2)n (3)k==j (4)a[i] == a[k] (5)a[k]==temp 2. (1) Inorder(BT一>left) (2) printf(" %c" (3) Inorder(B1-"- >right) 1371