当前位置：文档库 › 《数据结构》期末复习题-答案

《数据结构》期末复习题-答案

1.以下与数据的存储结构无关的术语是（ c ）

C、哈希表

2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）

B、108

3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ C ）

C、head–>next= =head

4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ D ）

D、2，3，5，1，6，4

5.下列关键字序列中，构成小根堆的是（ A ）

A、{12，21，49，33，81，56，69，41}

6.下列数据结构中，不属于二叉树的是（ A ）

A、B树

7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，若结点A[i]有右孩子，则其右孩子是（ C ）。

C、A[2i+1]

8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（ D ）

D、 8

9.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择

下面哪个序列输入（ B ）

B、37，24，12，30，53，45，96

10.对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ）

C、5，1，6，3，4，2

11.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( B )

B、[m/2]-1

12.散列文件也称为( C )

B 、索引文件

13.数据结构是（ D ）

D、相互之间存在一种或多种特定关系的数据元素的集合

14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ C ）

C、线性结构和树型结构

15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示

p指针所指向结点的表达式是（ D ）

D、p→llink→rlink

16.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的

底在V[m]，则栈满的条件是（ B ）

B、 top[1]+1=top[2]

17.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（ A ）

A、10

18.树的先根序列等同于与该树对应的二叉树的（ A ）

A、先序序列

19.下面关于哈希(Hash，杂凑)查找的说法正确的是( C )

C、不存在特别好与坏的哈希函数，要视情况而定

20.下列序列中，（ D ）是执行第一趟快速排序后所得的序列。

D、 [68，11，69，23，18] [93，73]

21.下列关键字序列中，构成小根堆的是( D )

D、 (15，28，46，37，84，58，62，41)

22.ISAM文件和VASM文件属于( C )

C、索引顺序文件

23.下面程序段的时间复杂度为（ C ）

for (i=0; i

for (j=0; j

A[i][j]=i*j;

C、O(m*n)

24.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所

指结点之后插入上述链表应执行的语句为（ A ）

A、q->next=s->next；s->next=p；

25.为便于判别有向图中是否存在回路，可借助于（ D ）

D、拓扑排序算法

26.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ D ）

D、SSSXXSXX

27.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少

应该是( B )

B、3

28.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头

元素所在的存储位置为（ B ）。

B、(rear-length+m)%m

29.在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ D ）。

D、rear->next=s;rear=s;

30.对于哈希函数H(key)=key%13,被称为同义词的关键字是（ D ）

D、25和51

31.采用二叉链表存储的n个结点的二叉树，共有空指针（ A ）个。

A、n+1

32.连通网的最小生成树是其所有生成树中（ D ）

D、边的权值之和最小的生成树

33.对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为（ B ）

B、508，314，123，145，486，298

34.任何一个无向连通图的最小生成树( C )。

C、一棵或多棵

35.无向图的邻接矩阵是一个( C )

C、对称矩阵

36.设无向图G-=(V,E)和G’=(V’,E’),如G’为G的生成树，则下列说法中不正确的是( B )。B、G’为G 连通分量

37.以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）

D、v1，v2，v5，v6，v7，v3，v4

38.下面几个符号串编码集合中，不是前缀编码的是（ B ）

B、{0,1,00,11}

39.希尔排序的增量序列必须是（B ）。

B、递减的

40.采用起泡排序法对n个关键字进行升序排序，若要使排序过程中比较关键字的次数最多，则初始时的序列应满足条件

（ D ）

D、关键字从大到小排列

41.在下列内部排序中( A )是不稳定的。

A 、希尔排序

42.

分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C )。

A 、（100，80， 90， 60， 120，110，130）

43.

在查找过程中，冲突指的是（ C ）。

C 、不同键值对应相同的存储地址

44.

对有14个元素的有序表A[1..14]作二分查找，查找元素A[4]时的被比较元素依次为（ D ）。

D 、A[7]，A[3]，A[5]，A[4]

45.

以v1为起始结点对下图进行广度度优先遍历，正确的遍历序列是（ A ）

A 、 v1，v2，v3，v4，v5，v6，v7

二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 1. 数据的物理结构包括数据元素的存储和数据之间关系的存储。

2. 若一个算法中的语句频度之和为T(n)=1921n+4nlogn,则算法的时间复杂度为 nlogn 。

下面程序段的时间复杂度是

n log 3 。

i=1；

while (i<=n) i=i*3；

循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front 和rear ，则当前队列的元素个数是（ rear-front+m ）% m 5. 主要是使插入和删除等操作统一 6. （n-1）/2 。

7. 在单链表中设置头结点的作用是深度优先。

线性表L=（a1,a2,…,an ）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是相同值关键字。 9.

已知一无向图G=（V ，E ），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a 开始遍历图，得到的序列为abecd ，则采用的是前移遍历方法。 10. 如果排序过程不改变时间复杂度之间的相对次序，则称该排序方法是稳定的。 11. 从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需出度一个位置。 12. 当问题的规模n 趋向无穷大时，算法执行时间T(n)的数量级被称为算法的 10 。

13.

若以邻接矩阵表示有向图，则邻接矩阵上第i 行中非零元素的个数即为顶点vi 的 sxssxxssxssxxx 。

14.一棵含999个结点的完全二叉树的深度为12 。

15.假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”

得到“ab*cd/+”的操作序列为 4 。

16..如图所示的有向无环图可以排出L->next->next==L

17.边种不同的拓扑序列。

18.从空树起，依次插入关键字1l，27，35，48，52，66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时

的平均查找长度为384 。

19.带头结点的双循环链表L中只有一个元素结点的条件是队列。

20.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中边稠密、边稀疏的数目正相关。

21.已知一棵完全二叉树中共有768结点，则该树中共有 5 个叶子结点。

22.实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需要8、64 存放被访问的结点以实现遍历。

23.Prim（普里姆）算法适用于求2h-1的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求2h-1 的网的最小生成树。

24.对长度为20的有序表进行二分查找的判定树的高度为n-1 。

25.设一棵完全二叉树有128个结点，则该完全二叉树的深度为n ，有_ 个叶子结点。

26.高度为h的完全二叉树中最少有栈个结点，最多有个结点。

27.设连通图G中有n个顶点e条边，则对应的最小生成树上有 3 条边。

28.构造n个结点的强连通图，至少有O(n2)条弧。

29.表达式求值是（42,13,94,55,05,46,17）应用的一个典型例子。

30.设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出

队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是。

31.快速排序算法在最差的情况下其时间复杂度是。

32.对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是。

三、应用题（本大题共5小题，每小题6分，共30分）

1.已知二叉树的先序遍历序列ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。

答案：二叉树形态

2.如图请给出邻接表、邻接矩阵及逆邻接表。

参考答案如下：

（1）邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1) vertex firstedge next

（2）逆邻接表：

（3）

由字符集{s ，t ，a ，e ，I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。

答案：原来的电文为：eatst

请画出下图所示的树所对应的二叉树，并写出对应二叉树的先序遍历和中序遍历。

答案：

先序遍历为：12345687 中序遍历为：34867521

1 2 3

5 6 7

1 2

6 7

5.设散列表为HT[13], 散列函数为H (key) = key %13。用闭散列法解决冲突, 对下列关键码序列12, 23, 45, 57, 20, 03, 78,

31, 15, 36 造表。采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。

答案：

使用散列函数H(key) = key mod 13，有

H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5,

H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5,

H(15) = 2, H(36) = 10.

利用线性探查法造表：

0 1 2 3 4 5 6 7 8 9 10 11 12

78 15 03 57 45 20 31 23 36 12

(1) (1) (1) (1) (1) (1) (4) (1) (2) (1)

搜索成功的平均搜索长度为

ASL succ =

(1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) =

6.已知带权图G如图所示，画出图G的一棵最小生成树。

答：

7.假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为

{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，请为这8个字母设计哈夫曼编码。

哈夫曼编码为：a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000

注意：答案不唯一

8.试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。

WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69 9.画出与如图所示森林对应的二叉树。

答：

10.已知一个散列表如下图所示：

35 20 33 48 59

0 1 2 3 4 5 6 7 8 9 10 11 12

其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法，探查序列为：

h i=(h(key)+i*h1(key))%m i=0,1,…，m-1

其中：h1(key)=key%11+1

回答下列问题：

（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？

（2）该散列表在等概率查找时查找成功的平均查找长度为多少？

答：

（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１；

（２）平均查找长度ASL=

++++

= 32112

11.请画出与下列二叉树对应的森林。

答：

12.对于给定结点的关键字集合K={5，7，3，1，9，6，4，8，2，10}，

（1）试构造一棵二叉排序树；

（2）求等概率情况下的平均查找长度ASL。

答：

（2）ASL=(1*1+2*2+3*4+4*3)/10=2.9

13.给出下图对应的邻接矩阵，并给出A，B，C三个顶点的出度与入度

答案: 邻接矩阵为：

A B C D E F

其中顶点A的入度为2，出度为1；

其中顶点B的入度为2，出度为2；

其中顶点C的入度为1，出度为3；

14.已知图5.32如下所示，求从顶点a到其余各顶点的最短路径。（给出求解过程）

答：

终点最短路径求解过程

b 6 (a,b) 5 (a,c,b)

c 3 (a,c)

d ∞ 6 (a,c,d) 6 (a,c,d)

e ∞ 7 (a,c,e) 7 (a,c,e) 7 (a,c,e)

f ∞ ∞ ∞ 9 (a,c,d,f) 9 (a,c,d,f) vj c b d e f S {a,c}

{a,c,b}

{a,c,d}

{a,c,e}

{a,c,d,f}

15.

阅读下列算法，并回答问题：

（1）假设串由合法的英文字母和空格组成，并以’\0’作结束符。设串s=”??I ?am ?a???student”(?表示空格符)，写

出f30（s ）的返回值；

（2）简述算法f30的功能。

int f30 (char*s)

答案：

(1) 4

(2)算法功能：统计单词的个数。

16.

阅读下列函数,并回答问题：

（1）假设队列q 中的元素为(a,b,c,d,e),其中“a ”为队头元素。写出执行函数调用Conv(&q)后的队列q ；（2）简述算法Conv 的功能。

答案：

（1）

e ，d ，c ，b ，a （2）

将队列里的值反转

17.

阅读下列函数,并回答问题：

已知整形数组L ［1..8］中的元素依次为（19，18，15，17，16，13，12，10），阅读下列函数，并写出执行函数调

用sort(L, 8)时，对L 进行的头两趟（pass 分别为0和1）处理结果。

3 2 2 3 3

5 6 a b d f c

答案：

（1）第一趟（pass = 0）19 15 18 16 17 12 13 10

（2）第二趟（pass = 1）19 15 16 18 12 17 10 13

18.已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的

长度为m，散列函数为Hash(key)=key%m。链表的结点结构为：。请在空缺处填入适当内容，使其成为一个完整

ke ne

算法。

［］, int m)

答案：

（1）NULL （2）p->next=H[j] p=q

19.下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下

操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。

答案：

（1）pre->next=pb （2）pre->next=pa （3）pre->next=pb

20.阅读算法f30，并回答问题：下列算法为有向图拓扑排序,请在空缺处填入合适的内容，使其成为一个完整的算法。

答案：

(1）top==-1 （2）top=graph[j].count （3）graph[k].count==0

21.阅读算法f31，并回答问题：下列算法功能为在数组a的前n(n>=1)个元素中找出第k(1<=k<=n)小的值。这里假设数组

a中各元素的值都不相同。请在空缺处填入合适的内容，使其成为一个完整的算法。

答案：

（1）(i==k) return; （2）i+1 （3）i-1

22.阅读算法f33，并回答问题：下列算法功能为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[i+1]进行

比较,第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],将二者交换;以后重复上述二趟过程,直至整个数组有序。请在空缺处填入合适的内容，使其成为一个完整的算法。

答案：

(1)a[i]=t (2)(i=2;i<=n;i+=2) (3)flag

四、算法设计题（本大题共2小题，每小题10分，共20分）

1.已知单链表的结点类型为Lnode，包含next和data成员。编写算法，实现带头结点单链表的逆置算法。

参考答案：

void invent(Lnode *head)

{

Lnode *p,*q;

if(!head->next) return ERROR;

p=head->next; q=p->next; p->next =NULL;

while(q)

{p=q; q=q->next; p->next=head->next; head->next=p;}

}

2.编写一个函数，要求借助一个栈把一个数组中的数据元素逆置。

其中，栈类型为SeqStack，可以直接使用InitStack(SeqStack**)、

Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函数。

参考答案：

void Inverse(ElemType arr[],int n)

{

SeqStack *s;

int i;

InitStack(&s);

for(i=0;i

Push(s,arr[i]);

for(i=0;i

Pop(s,&arr[i]);

}

3.二叉树采用链接存储结构，结点类型为Btree，包括left、right和data三个成员，试设计一个算法计算一棵给定二叉

树的度为2的结点的个数。

参考答案：

int twochild(Btree *b)

{ int num1,num2;

if (b==NULL) return 0;

else

{ num1=twochild1(b->left);

num2=twochild1(b->right);

if ( b->left!=NULL&&b->right!=NULL) return (num1+num2+1);

else return (num1+num2);

}

4.假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示：

typedef char DataType;

typedef struct node {

DataType data;

struct node *lchild, *rchild; //左右孩子指针

struct node *parent; //指向双亲的指针

} BinTNode;

typedef BinTNode *BinTree;

若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。

(1)就后继的不同情况，简要叙述实现求后继操作的方法；

参考答案：

（1）分两种情况讨论

①当*px的右子树不为空时，则从*px的右孩子开始，沿其左孩子往下查找，直到找到一个没有左孩子的节点为止，则该

结点为*px在中序序列中的后继；

②当*px的右孩子为空时，则沿*px的双亲指针链向上查找，直至找到其左子树中包含*px的最年轻祖先，则该祖先结点

为*px在中序序列中的后继。

(2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。

（2）BinTree f34(BinTree px)

{

BinTree q=px->rchild;

if(q!=NULL){//沿左孩子往下查找

px=q;

while(px->lchild!=NULL)

px=px->lchild;

}

else{//沿双亲指针链向上查找

while(px!=NULL && px->rchild==q){

q=px;

px=px->parent;

}

return px;//返回所找到的中序序列后继结点的指针

//或者无后继结点时返回空指针

}

5.已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。

参考答案：

void AllSPdfs(AdjList g,vertype u,vertype v)

{ //求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(g,u,v)

int top=0,s[];

s[++top]=u; visited[u]=1;

while (top>0 || p)

{

p=g[s[top]].firstarc; //第一个邻接点。

while (p!=null && visited[p->adjvex]==1) p=p->next; //下一个访问邻接点表。

if (p==null) top--; //退栈。

else {

i=p->adjvex; //取邻接点（编号）。

if (i==v) //找到从u到v的一条简单路径，输出。

{

for (k=1;k<=top;k++)

printf( "%3d",s[k]); printf( "%3d\n",v);}//if

else { visited[i]=1; s[++top]=i; } //else深度优先遍历。

}//else

}//while

}// AllSPdfs

6.已知有n个顶点的有向图邻接表，编写一个函数求出该图中指定顶点的出度。已知边类型edgenode，包含next和adjvex

（序号）成员。类型adjlist表示顶点数组类型，每个数组元素包含link和vex成员。

参考答案：

int outdegree(adjlist adj,int v)

{ int degree=0;

edgenode *p;

p=adj[v].link;

while(p!=NULL)

{ degree++;

p=p->next;

}

return degree;

}

7.编写算法实现对给定的二叉树是否为二叉排序树的判别。设二叉树以二叉链表存储表示。（要求写出二叉链表的类型定义）

参考答案：

//二叉树的二叉链表表示

typedef struct BINTREENODE

{ ElemType data;

struct BINTREENODE *lchild, rchild;

} BinNode,*BinTree //答对给2分

i nt BsBtr(BinTree t, BinTree pre, int flag)

{ //判别给定的二叉树是否为二叉排序树

pre =NULL; flag=TRUE;

if (t && flag)

{ BSBtr(t->lchild, pre, flag);

if (pre = = NULL) { flag=TRUE；pre=t; }

else if(pre->key < t->key) //比较t 与中序直接前驱pre的大小

{ flag=TRUE; pre=t;} //pre与t有序

else flag=FALSE; //pre与t无序

}//if

BSBtr(t->rchild,pre,flag);

}//BSBtr

数据结构模拟题(开卷)

《数据结构》模拟题（补）一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1，则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i

数据结构模拟试题及答案

数据结构模拟试题一一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素

操作系统期末试题及答案

操作系统期末试题及答案文件编码（008-TTIG-UTITD-GKBTT-PUUTI-WYTUI-8256）

（答案在后面）一、填空题(每空1分,共10分) 1. 常见的I/O 控制方式有程序I/O 方式、中断 I/O 控制方式、 DMA I/O 控制方式和通道 I/O 控制方式四种。 2. 操作系统向用户提供的两个基本接口是程序接口和用户接口。 3. 若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024 字节，逻辑地址(3082)10转化得到的物理地址是 6154 。 4. 具有多路性、独立性、及时性和交互性特征的操作系统是分时操作系统。 5. 通道用于控制设备控制器与内存之间的信息交换。 6. 事务的最基本特性是。 7. 若盘块大小为4KB ，每个盘块号占4字节，在采用两级索引时允许的最大文件长度为 4GB 。二、单选题(每题2分,共20分) 1. 用磁带作为文件存贮介质时，文件只能组织成 ( )。 A. 顺序文件 B. 链接文件 C. 索引文件 D. 目录文件 2. 一作业8：00到达系统，估计运行时间为1小时，若10：00开始执行该作业，则其响应比是( C )。 A. 2 B. 1 C. 3 D. 3. 文件系统采用多级目录结构后，对于不同用户的文件，其文件名( C )。

A. 应该相同 B. 应该不同 C. 可以相同，也可以不同 D. 受系统约束 4.死锁预防是保证系统不进入死锁状态的静态策略，其解决方法是破坏产生死锁的四个必要条件之一。下列方法中破坏了“循环等待”条件的是（ D ）。 A. 银行家算法 B. 一次性分配策略 C. 剥夺资源法 D. 资源有序分配法 5.进程状态从就绪态到运行态的转化工作是由（ B ）完成的。 A. 作业调度 B. 进程调度 C. 页面调度 D. 设备调度 6.采用缓冲技术的主要目的是（ C ）。 A. 改善用户编程环境 B. 提高CPU的处理速度 C. 提高CPU和设备间的并行程度 D. 实现与设备无关性 7.目录文件所存放的信息是（ D ）。 A. 该目录中所有数据文件目录 B. 某一文件存放的数据信息 C. 某一个文件的文件目录 D. 该目录中所有文件的目录 8.最容易形成很多小碎片的可变分区分配算法是（ D ）。 A. 首次适应算法 B. 循环首次适应算法 C. 最坏适应算法 D. 最佳适应算法 9.用户程序与实际使用的物理设备无关是由（ A ）功能实现的。 A. 设备独立性 B. 设备驱动 C. 虚拟设备 D. 设备分配 10.下面关于顺序文件、链接文件和索引文件的论述中不正确的是（ A ）。 A. 显示链接文件是在每个盘块中设置一个链接指针，用于将该文件所属的所有盘块链接起来 B. 顺序文件必须采用连续分配方式，而链接文件和索引文件则都可采取离散分配方式 C. 顺序文件适用于对诸记录进行批量存取时

2017年数据结构期末考试题及答案A

2017年数据结构期末考试题及答案一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出

8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点

《数据结构C》模拟试题

山东科技大学继续教育学院《数据结构C》模拟试题一班级姓名学号一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。

操作系统期末考试试题和标准答案及评分标准汇编

《操作系统》试题（A卷）（考试时间：90分钟）一、选择题（共20分，每小题1分） 1．（）不是基本的操作系统。 A.批处理操作系统 B.分时操作系统 C.实时操作系统 D.网络操作系统 2．现代OS具有并发性和共享性，是（）的引入导致的。 A.单道程序 B. 磁盘 C. 对象 D.多道程序 3．一般来说，为了实现多道程序设计，计算机最需要（）。 A.更大的内存 B.更多的外设 C.更快的 CPU D.更先进的终端 4．在下面的I/O控制方式中，需要CPU干预最少的方式是（）。 A.程序I/O方式 B.中断驱动I/O控制方式 C.直接存储器访问DMA控制方式 D.I/O通道控制方式 5．在进程状态转换时，下列（）转换是不可能发生的。 A.就绪态→运行态 B.运行态→就绪态 C.运行态→阻塞态 D.阻塞态→运行态 6．一个进程执行过程中不可能对应( )。 A.一个PCB B.一个JCB C.多个PCB D.一个程序 7．进程调度又称为低级调度，其主要功能是( )。 A.选择一个作业调入内存 B.选择一个主存中的进程调出到外存 C.选择一个外存中的进程调入到主存 D.将一个就绪的进程投入运行 8．如果允许不同用户的文件可以具有相同的文件名，通常采用（）来保证按名存取的安全。 A.重名翻译机构 B.建立索引表 C.建立指针 D.多级目录结构 9．文件控制块不包括（）。 A.文件名 B.文件访问权限说明 C.文件物理位置信息 D.磁盘坏块信息10．为了提高设备分配的灵活性，用户申请设备时应指定（）号。 A.设备类相对 B.设备类绝对 C.相对 D.绝对 11．若进程P一旦被唤醒就能够投入运行，系统可能为( )。 A.在分时系统中，进程P的优先级最高。

《数据结构》模拟试卷一及答案

模拟试卷一一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( )

(完整版)操作系统期末试卷(含答案)

一、选择题 1、在现代操作系统中引入了（），从而使并发和共享成为可能。 A.单道程序 B. 磁盘 C. 对象 D.多道程序 2、( )操作系统允许在一台主机上同时连接多台终端，多个用户可以通过各自的终端同时交互地使用计算机。 A.网络 B.分布式 C.分时 D.实时 3、从用户的观点看，操作系统是（）。 A. 用户与计算机硬件之间的接口 B.控制和管理计算机资源的软件 C. 合理组织计算机工作流程的软件 D.计算机资源的的管理者 4、当CPU处于管态时，它可以执行的指令是（）。 A. 计算机系统中的全部指令 B. 仅限于非特权指令 C. 仅限于访管指令 D. 仅限于特权指令 5、用户在程序中试图读取某文件的第100个逻辑块时，使用操作系统提供的（）接口。 A. 系统调用 B.图形用户接口 C.原语 D.键盘命令 6、下列几种关于进程的叙述，（）最不符合操作系统对进程的理解？ A.进程是在多程序并行环境中的完整的程序。 B.进程可以由程序、数据和进程控制块描述。 C.线程是一种特殊的进程。 D.进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。 7、当一个进程处于（）状态时，称其为等待（或阻塞）状态。 A. 它正等待中央处理机 B. 它正等待合作进程的一个消息 C. 它正等待分给它一个时间片 D. 它正等待进入内存 8、一个进程释放一种资源将有可能导致一个或几个进程（）。 A.由就绪变运行 B.由运行变就绪 C.由阻塞变运行 D.由阻塞变就绪 9、下面关于线程的叙述中，正确的是（）。 A.不论是系统支持线程还是用户级线程，其切换都需要内核的支持。 B.线程是资源的分配单位，进程是调度和分配的单位。 C.不管系统中是否有线程，进程都是拥有资源的独立单位。 D.在引入线程的系统中，进程仍是资源分配和调度分派的基本单位。 10、设有3个作业，它们同时到达，运行时间分别为T1、T2和T3,且T1≤T2≤T3，若它们在单处理机系统中按单道运行，采用短作业优先调度算法，则平均周转时间为（）。 A. T1+T2+T3 B. (T1+T2+T3)/3 C. T1+T2/3+2*T3/3 D.T3/3+2*T2/3+T1 11、在下面的I/O控制方式中，需要CPU干预最少的方式是（）。 A．程序I/O方式B．中断驱动I/O控制方式C．直接存储器访问DMA控制方式D．I/O通道控制方式 12、有m个进程共享同一临界资源，若使用信号量机制实现对一临界资源的互斥访问，则

数据结构复习资料,java数据结构期末考试

第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析：如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长

《数据结构》期末考试题及答案

2011-2012学年第一学期期末考查《数据结构》试卷（答案一律写在答题纸上，在本试卷上做答无效）一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序

数据结构模拟试卷(含答案)

数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。

A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆

操作系统期末测试题2套带答案

中央广播电视大学第二学期“开放本科”期末考试计算机专业计算机操作系统试题、选择题(选择一个正确的答案的代号填入括号中。每空 2 分，共50 分) 1 ．既考虑作业等待时间，又考虑作业执行时间的调度算法是( )． A. 响应比高者优先 B.先来先服务 C. 比先级调度 D. 短作业优先 2 .作业调度程序从处于()状态的队列中选择适当的作业投入运行. A. 运行 B.提交 C. 完成 D. 后备 3.进程的并发执行是指两个以上的进程(). A. 同时执行 B.在执行的时间上是重叠的 C. 在执行的时间上是不可重叠的 D .共享系统资源 4 ．在下列解决死锁的方法中，属于死锁预防策略的是( )。 A?银行家算法B.资源有序分配法 C.死锁检测法 D ?资源分配图化简法 5.系统“抖动”现象的发生不是由( )引起的. A. 置换算法选择不当 B. 交换的信息量过大 C. 主存容量不足 D.请求页式管理方案 6 .在动态分E存储管理中的紧凑(移动)技术可以()。 A .集中空闲区 B .增加主存容量 C. 缩短访问周期 D .加速地址转换 7. 在请求分页存储管理中，若采用FIFO 页面替换算法，则当分配的页面数增加时，缺页中断次数( )。 A. 减少 B.增加 C.无影响 D ?可能增加也可能减少 8. 用V 操作唤醒一个等待进程时，被唤醒进程的状态转换为( )。 A. 等待 B. 就绪 C. 运行 D .完成 9. 下面对进程的描述中，错误的是( )。 A.进程是动态的概念 B.进程执行需要处理饥 C.进程是有生命期的 D ?进程是指令的集合 10. 作业执行中要不断启动外部设备，通常把存储介质上的信息读入主存或者把主存中的信息送到存储介质上的操作称为( )操作。 A. 输入输出 B. 启动外设 C.访问主存 D .作业执行 11 . CPU 与通道可以并行执行，并能通过( )实现彼此之间的通信。 A. I／O 指令 B. I／O 中断 C. 操作员 D. I／O 指令和I／O 中断 12 .分布式操作系统与网络操作系统本质上的不同在于( )。

2017数据结构期末考试试题及答案

2017《数据结构》期末考试试题及答案《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1.

数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是（）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时（）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？（） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（）个，位置在 676（10），每个元素占一个空间，表示用 10 进制表示。问 A[3][3] （10）存放在什么位置？脚注（10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示（）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据二叉树的第 k 层的结点数最多为（）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7.

数据结构期末模拟试题05(有答案)

课程测试试题（卷） ----------------------以下为教师填写-------------------- I、命题院（部）：数学与计算机科学学院 II、课程名称：数据结构 III、测试学期：20 －20 学年度第学期 IV、测试对象：学院专业级班 V、问卷页数（A4）：页 VI、答卷页数（A4）：页 VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚） VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为 ( )。

以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 _________，在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是 ________________;删除一个结点时，需要执行的操作是 ______________________________（假设栈不空而且无需回收被删除结点）。

操作系统期末试题(含答案)

操作系统期末考试（A） 1、文件系统的主要组成部分是（ D ） A、文件控制块及文件 B、I/O文件及块设备文件 C、系统文件及用户文件 D、文件及管理文件的软件 2、实现进程互斥可采用的方法（C） A、中断 B、查询 C、开锁和关锁 D、按键处理 3、某页式管理系统中，地址寄存器的低9位表示页内地址，则页面大小为（B） A、1024字节 B、512字节 C、1024K D、512K 4、串联文件适合于（B）存取 A、直接 B、顺序 C、索引 D、随机 5、进程的同步与互斥是由于程序的（D ）引起的 A、顺序执行 B、长短不同 C、信号量 D、并发执行 6、信号量的值（D ） A、总是为正 B、总是为负 C、总是为0 D、可以为负整数 7、多道程序的实质是（B） A、程序的顺序执行 B、程序的并发执行 C、多个处理机同时执行 D、用户程序和系统程序交叉执行 8、虚拟存储器最基本的特征是（A） A、从逻辑上扩充内存容量 B、提高内存利用率 C、驻留性 D、固定性 9、飞机定票系统是一个（A ） A、实时系统 B、批处理系统 C、通用系统 D、分时系统 10、操作系统中，被调度和分派资源的基本单位，并可独立执行的实体是（C） A、线程 B、程序 C、进程 D、指令二、名词解释（每小题3分，共15分） 1.死锁: 多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程将永远不能再向前推进 2.原子操作: 一个操作中的所有动作要么全做，要么全不做，它是一个不可分割的操作。 3.临界区: 在每个进程中访问临界资源的那段代码 4.虚拟存储器: 是指仅把作业的一部分装入内存便可运行作业的存储器系统。也即是具有请求调入功能和置换功能，能从逻辑上进行扩充的一种存储系统。 5.文件系统: 是指含有大量的文件及其属性的说明，对文件进行操纵和管理的软件，以及向用户提供的使用文件的接口等的集合三、判断改错题（判断正误，并改正错误，每小题2分，共20分） 1、通道是通过通道程序来对I/O设备进行控制的。（T） 2、请求页式管理系统中，既可以减少外零头，又可以减少内零头。（） 3、操作系统中系统调用越多，系统功能就越强，用户使用越复杂。（） 4、一个进程可以挂起自已，也可以激活自已。（T ） 5、虚拟存储器的最大容量是由磁盘空间决定的。（） 6、单级文件目录可以解决文件的重名问题。（） 7、进程调度只有一种方式：剥夺方式。（） 8、程序的顺度执行具有顺序性，封闭性和不可再现性。（） 9、并行是指两个或多个事件在同一时间间隔内发生，而并发性是指两个或多个事件在同一时刻发生。（） 10、进程控制一般都由操作系统内核来实现。（）四、简答题（每小题5分，共25分） 3、简述死锁产生的原因及必要条件。答：死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程将永远不能再向前推进。产生死锁的原因可归结为两点：（1）争资源。（2）进程推进顺序非法。在具备下述四个必要条件时，就会产生死锁。（1）互斥条件（2）请求和保持条件

《数据结构》期末复习题-答案

数据结构模拟题(开卷)

最新计算机操作系统期末考试题及答案

数据结构模拟试题及答案

操作系统期末试题及答案

2017年数据结构期末考试题及答案A

《数据结构C》模拟试题

操作系统期末考试试题和标准答案及评分标准汇编

《数据结构》模拟试卷一及答案

(完整版)操作系统期末试卷(含答案)

数据结构复习资料,java数据结构期末考试

《数据结构》期末考试题及答案

数据结构模拟试卷(含答案)

操作系统期末测试题2套带答案

2017数据结构期末考试试题及答案

数据结构期末模拟试题05(有答案)

操作系统期末试题(含答案)