桂林电子科技大学攻读工程硕士专业学位专业课考试试题
2010年在职攻读工程硕士专业学位
第二阶段专业课考试试题
学位类别名称： 工程硕士
工程领域名称： 计算机技术
专业课名称： 数据结构与程序设计
考生须知
1．答案必须写在答题纸上，写在试题上无效。
2．答题时一律使用蓝、黑色墨水笔作答，用其它笔答题不给分。
3．交卷时，请配合监考人员验收，并请监考人员在准考证相应位置签字（作为考生交卷的凭
据）。否则，产生的一切后果由考生自负。
第1页 共 8 页
桂林电子科技大学攻读工程硕士专业学位专业课考试试题
一、选择题（18×2=36分）
1、在下面的程序段中，对x的赋值语句的频度为（ ）
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) x=x+1;
2n
A． O(2n) B．O(n) C．O(n) D．O(log2)
2、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
3、 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。
A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
4、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）
A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG
5、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 47 84 25 15 21 （3） 47 25 84 15 21 （4） 47 25 15 84 21 则采用的排序是 ( )。
A. 选择 B. 冒泡 C. 快速 D. 插入
6、在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( )。
注:双向链表的结点结构为(llink,data,rlink)。 供选择的答案：
A． p->llink=q； q->rlink=p； p->llink->rlink=q； q->llink=q；
B． p->llink=q； p->llink->rlink=q；q->rlink=p；q->llink=p->llink； C． q->rlink=p；q->llink=p->llink；p->llink->rlink=q; p->llink=q; D． q->llink=p->llink；q->rlink=p； p->llink=q；p->llink=q；
7、下面的答案中那一个是图的拓扑序列（ ）。 A. A-B-C-F-E-D B. D-B-A-C-E-F C. A-D-C-B-E-F D. D-E-B-A-C-F
A F E D B C 7 题图
8、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A．求子串 B．联接 C．匹配 D．求串长
第2页 共 8 页
桂林电子科技大学攻读工程硕士专业学位专业课考试试题
9、下列排序算法中，占用辅助空间最少的是：( ) 。
A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序
10、从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构
11、一个顺序表的第一个元素的存储地址是100，每个元素的长度为5，则第7个元素的地址是（ ）。
A．130 B. 125 C. 120 D. 135
12、如果以链表作为栈的存储结构，则入栈操作时（ ）。 A. 必须判别栈是否满
B. 必须判别栈是否为空 D. 可不做任何判断
C. 必须判别栈元素类型
13、下列排序方法中，哪一个是稳定的排序方法？（ ）。
A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序
14、顺序结构的本质特点是（ ）。
A. 数据元素存储在地址连续的内存空间
B. 数据元素紧邻
C. 数据元素在内存中的相对位置表示数据之间的逻辑关系 D. 不使用指针
15、某内排序方法的稳定性是指( )。
A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对
16、算法的效率的分析主要包括两个方面（ ）。
A. 时间复杂度和空间复杂度 B. 正确性和简单性
C. 可读性和文档性 D. 数据复杂性和程序复杂性
17、输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）
A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop
18、对于顺序存储的线性表，访问结点和增加结点的时间复杂度为（ ）。
A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
第3页 共 8 页
桂林电子科技大学攻读工程硕士专业学位专业课考试试题
二、解答题（共5题，共计38分）
1、设A、B、C、D、E、F六个字母出现的概率分别为8,19,12,16,32,13。试写出为这六个字母设计的HUFFMAN编码, 并画出对应的HUFFMAN树。(设计编码5分，画哈夫曼树6分，本题共计11分)。
2、已知完全二叉树有30个结点，则整个二叉树有多少个度为0的结点？（本题共计
第4页 共 8 页
5分）
