当前位置:问答库>考研试题

2017年华北电力大学(北京)控制与计算机工程学院842数据结构与操作系统之数据结构考研导师圈点必考题汇编

  摘要

一、填空题

1. 属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

2. 在有n 个顶点的有向图中,每个顶点的度最大可达。

【答案】2(n-l )

【解析】当有向图为完全连通图时每个顶点的度达到最大,出度入度均为n-1。

3. 在单链表中设置头结点的作用是_____。

【答案】方便运算

4. 二叉树由_____,_____,_____三个基本单元组成。

【答案】根结点;左子树;右子树

5. 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。

【答案】

6. 以下是用类C 语言写山的算法,该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表,链接时,结点的Lchild 域作为前链域,指向结点的直接前驱,结点的Rchild 域作为后链域,指向结点的直接后继。算法中,使用一个顺序栈stack , 栈顶head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针,试填充算法中的空格,使算法完整。

void leafchain(BiTree Abt)

{p={BiTree)malloc (sizeof (BiTNode )); If (!p ){print£(“OVERFLOW\n”; exit (1); }

head=p; top=0; if (bt )

{top++; stack[top]=bt; while (top )

{t=stack[top]; top--;

if (it->Lchild && !t->Rchild){ (1) ; (2) ; (3) ; } else {if( (4) ){top++; stack[top]= (5) ; }

if ( (6) ){top++; stack[top]= (5) ; } } }

(8) ; (9) ; } } 【答案】

p->Rchild=t:t->Lchild=p:p=t: t->Rchild!=null:t->Rchild: t->Lchild!=null: t->Lchild: p->Rchild=head:head->Lchild=p

7. 当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便,但插入和删除操作不如链式存储结构方便,而且需要连续的存储空间,由于该线性表的元素总数基本稳定,而且很少进行插入删除操作,为了更快的存取元素,顺序表更合适。

8. —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

9. 串是一种特殊的线性表,其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符;顺序存储;链式存储;串的长度相等且两串中对应位置的字符也相等

10.

每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。

【答案】

前序是。

11.设单链表的结点结构为

【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的

.

,则它的后庁序列是_____。设上述二叉树是由某棵树转换而成,则该树的

为指针域,已知指针px 指向单链表中data 为x 的结

_____;点,指针py 指向data 为y 的新结点,若将结点y 插入结点x 之后,贝懦要执行以下语句:_____;

【答案】

12.设有个结点的完全二叉树顺序存放在向量中,其下标值最大的分支结点为_____。

【答案】

【解析】最大的分支结点是最后一个叶子结点的父结点。

二、选择题

13.分别以下列序列构造二叉排序树,与用其他三个序列所构造的结果不同的是( )。

【答案】C

【解析】二叉排序树:左右子树都是二叉排序树,且保证右子树都比根结点大,左子树都比根结点小。据以上两点建立二叉排序树。

14.某计算机采用二级页表的分页存储管理方式,按字节编址,页大小为2字节,逻辑地址结构为:

逻辑地址空间大小为( )。

A.64 B.128 C.256 D.512

【答案】B

【解析】地址空间分为逻辑地址空间和物理地址空间。页的大小为采用二级页表,一页可存放要

15.折半查找的时间复杂性为( )。

【答案】D

【解析】顺序查找的事件复杂度为度为

位的DRAM 芯片构成,该DRAM 芯片的地址引脚

16.某容量为256M 的存储器,由若干和数据引脚总数是:( )

A.19 B.22 C.30 D.36

【答案】A

【解析】DRAM 地址线复用,4M 为2的22次方,因此除2为11根,数据线8根。因此地址引脚和数据引脚总数为19根

因为折半查找是查找效率最高的算法,它的事件复杂

个页面来保存页表项,故本题答案为B 。

字节,页表项大小为2B ,

字节,故最少需

’个页表项,本题中逻辑地址空间大小为

页,则表示整个逻辑地址空间的页目录表中包含表项的个数至少是

字节,页表项大小为