手机APP下载

您现在的位置: 首页 > 考研英语 > 考研专业课 > 青岛大学 > 正文

青岛大学2005年数据结构专业课考研真题试卷

来源:可可英语 编辑:max   可可英语APP下载 |  可可官方微信:ikekenet

一.单项选择题(本大题共10道小道小题,每小题3分,共30分)

1. 算法的时间复杂度取决于【 】

A. 问题的规模 B. 待处理数据的初始状态

C. 软件和硬件的组合 D. 操作系统

2. 向一个栈顶指针为top的链栈中插入一个s结点,则执行 【 】

A. top->next=s; B. s->next=top->next; top->next=s;

C. s->next=top; top=s; D. s->next=top; top=top->next;

3.广义表((a))的表头是【 】

A. a B. (a) C. () D. ((a))

4. 由带权为8、2、5、7的叶子结点构造一棵哈夫曼树,该树的带权路径长度为 【 】

A. 37 B. 32 C. 46 D. 43

5. 采用邻接表存储的图,其BFS算法类似于二叉树的【 】

A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层遍历

6. 在非空m阶B_树上,除根结点之外的所有其他非终端结点【 】

A. 至少有2/m棵子树 B. 至多有2/m棵子树

C. 至少有2/m棵子树 D. 至多有2/m棵子树

7. 对线性表进行顺序查找时,要求线性表的存储结构为【 】

A. 散列存储 B. 顺序存储或者链式存储

C. 压缩存储 D. 索引存储

8. 在关键字“基本有序”的情况下,最佳排序算法为 【 】

A. 快速排序 B. 冒泡排序 C. 直接插入排序 D. 基数排序

9. 折半查找法和二叉排序树的时间性能【 】

A. 与处理数据量有关 B. 相同 C. 不相同 D. 不确定

10. 串是一种特殊的线性表,其特殊性体现在【 】

A. 可以顺序存储 B. 数据元素是一个字符

C. 可以链接存储 D. 数据元素可以是多个字符

二、填空题(本大题共10小题,每小题2分,共20分)

1. 在具有n个单元的循环队列中,队满时共有____________个元素。

2. 单链表中设置头结点的目的是____________。

3. 消除递归_____________需要使用栈。

4. 在具有n(n≥1)个结点的k叉树中,有_____________个空指针。

5. 深度为5的二叉树至多有_________个结点。

6. 一个连通图的__________是一个极小连通子图。

7. 对稀疏图进行DFS遍历时,应该采用___________作为其存储结构。

8. 在哈希表中,装填因子α越大,则_______________________。

9. 在堆排序和快速排序中,若原始记录接近有序,则应该选择____________。

10. 设关键字序列为{3, 7, 6, 9, 7, 1, 4, 5, 20},对其排序的最少交换次数为_________。

三、简答题(本大题共6道小题,共56分)

1. 若中序序列为ABC,试问有多少种不同的形态的二叉树可以得到这一遍历结果?画出所有的二叉树。(9分)

2. 对于下图,请给出:

(1) 对应的邻接矩阵,并给出V1、V2、V3的出度和入度;

(2) 邻接表和逆邻接表;

(3) 强连通分量。(10分)

3. 已知关键字序列为{9, 6, 2, 5, 4, 3, 1, 10, 7, 11, 8},试回答: (1) 按表中元素的顺序,构造一棵平衡二叉排序树。 (2) 在等概率的情况下,求查找成功的ASL值。(10分)

4. 在采用线性探测再散列法解决冲突的散列表中,所有同义词在表中是否一定相邻?试说明理由。(9分)

5. 有关键字{25, 50, 55, 20, 30, 45, 40, 15, 10, 35},判断其是否为堆,若不是堆,请调整为一个小根堆。要求写出调整过程。(9分)

6. 什么是内部排序?稳定性指的是什么?(9分)

四、算法阅读题(本大题共3道小题,每小题8分,共24分)

【说明】结构定义

struct ListNode { elemtype data;

struct ListNode *next; };

struct BtreeNode { elemtype data;

struct BtreeNode *lchild, *rchild; };

1. 下面算法的功能是将队列中的数据元素进行逆置。设栈和队列的元素类型均为int。请在空白处填入正确的语句。

Void unknown(queue &q) {

__________①_________; int d; InitStack(s);

while(_______②_______){ Dequeue(q, d); Push(s, d); }

while(!StackEmpty(s)){ _______③______; Enqueue(q, d); } }

2. 下面的算法是统计单链表中数据域的值为X的结点个数。请在空白处填入正确的语句。

int CountNodeX(struct ListNode *head, Elemtype x) {

struct ListNode *p; _______①______; p = head;

while(______②_____){

if(_______③______) n++; p=p->next; }

________④_________; }

3. 下面的算法完成了对一棵二叉树中所有的左、右子树的相互交换。请在空白入填入正确的语句。

Void TNodeExchang(struct BTreeNode *root) {

if(________①________){

TNodeExchang(root->lchild); _________②__________; struct BTreeNode *p; p = _______③_________;

root->lchild = root->rchild; root->rchild = _______④______; } }

五、算法设计题(本大题共3道小题,共20分)

1. 已知Head是带头结点的单链表的头指针,试编写逆序输出表中各元素的递归算法。假设数据为整数。

Void FindLinkData(struct ListNode *head) {…}(7分)

2. 试设计一个算法,求出指定结点在给定的二叉排序树中的层次。 【要求】1. 给出算法的设计思想; 2. 给出算法代码。(7分)

int pLevel(struct BTreeNode *root, struct BTreeNode *p) {//求指定结点p在以root为根的二叉树中的层次} 3. 给出一棵二叉树的前序序列和后序序列,能否唯一地确定一棵二叉树?试证明你的论断。(6分)

重点单词   查看全部解释    
unknown ['ʌn'nəun]

想一想再看

adj. 未知的,不出名的

 
void [vɔid]

想一想再看

adj. 空的,无效的,空虚的
n. 真空,空

 

发布评论我来说2句

    最新文章

    可可英语官方微信(微信号:ikekenet)

    每天向大家推送短小精悍的英语学习资料.

    添加方式1.扫描上方可可官方微信二维码。
    添加方式2.搜索微信号ikekenet添加即可。