当前位置：文档之家› 自考数据结构历年试题及答案

自考数据结构历年试题及答案

全国2001年10月高等教育自学考试

数据结构试题

课程代码：02331 第一部分选择题(30分)

7．若目标串的长度为n ，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的

时间复杂度是（ C ） A ．O （n 3

） B ．O （n ） C ．O （n 2） D ．O （n 3） 8．一个非空广义表的表头（ D ）

A ．不可能是子表

B ．只能是子表

C ．只能是原子

D ．可以是子表或原子 9

对应的稀疏矩阵是（ A ）

0806

7000

0000

5040

0000

0806

7000

5040

0000

0300

0806

0000

0200

5040

0000

0806

0000

7000

5040

0300

10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( C )

A．4 B．5 C．6 D．7

11．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D ) A．e B．2e C．n2－e D．n2－2e

12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点v i相关的所有弧的时间复杂度是( C )

A．O(n) B．O(e) C．O(n+e) D．O(n*e)

13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：

20，15，21，25，47，27，68，35，84

15，20，21，25，35，27，47，68，84

15，20，21，25，27，35，47，68，84

则所采用的排序方法是（ D ）

A．选择排序B．希尔排序C．归并排序D．快速排序

14．适于对动态查找表进行高效率查找的组织结构是（C ）

A．有序表B．分块有序表C．三叉排序树D．线性链表

15．不定长文件是指（B ）

A．文件的长度不固定B．记录的长度不固定

C．字段的长度不固定D．关键字项的长度不固定

第二部分非选择题（共70分）

二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不

写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。

16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储（存储结构）无关，是独立于计算机的。

17．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head 可用p表示为head= p->next->next 。

18．栈顶的位置是随着进栈和退栈操作而变化的。

19．在串S=“structure”中，以t为首字符的子串有12 个。

20．假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B[0]存储

矩阵中第1个元素a 1,1,则B[31]中存放的元素是。

21．已知一棵完全二叉树中共有768结点，则该树中共有 384 个叶子结点。 22．已知一个图的广度优先生成树如右图所示，则与此相应的广度优先遍历序列为 abefcdg 。

23．在单链表上难以实现的排序方法有快速排序和堆排序。 24．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 2 。 25．多重表文件和倒排文件都归属于文件。三、解答题（本大题共4小题，每小题5分，共20分） 26．画出下列广义表的共享结构图形表示 P=（（（z ）,(x,y)）,((x,y),x),(z)） 27．请画出与下列二叉树对应的森林。

28．已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示

0100110010000110110110110???

???????

?????

? (1)画出该图的图形；

（2）根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。

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）该散列表在等概率查找时查找成功的平均查找长度为多少？四、算法阅读题（本大题共4小题，每小题5分，共20分）

b c

d e

30．下列算法的功能是比较两个链串的大小，其返回值为：

comstr(s1,s2)=

当

s s

请在空白处填入适当的内容。

int comstr(LinkString s1,LinkString s2)

{//s1和s2为两个链串的头指针

while(s1&&s2){

if(s1－>datedate)return－1；

if(s1－>date>s2－>date)return1；

①；

②；

}

if( ③)return－1；

if( ④)return1；

⑤；

}

①

②

③

④

⑤

31．阅读下面的算法

LinkList mynote(LinkList L)

{//L是不带头结点的单链表的头指针

if(L&&L->next){

q=L；L=L－>next；p=L；

S1：while(p－>next) p=p－>next；

S2：p－>next=q；q－>next=NULL；

}

return L；

}

请回答下列问题：

（1）说明语句S1的功能；

（2）说明语句组S2的功能；

（3）设链表表示的线性表为（a1,a2, …,a n）,写出算法执行后的返回值所表示的线性表。

32．假设两个队列共享一个循环向量空间（参见右下图），

其类型Queue2定义如下：

typedef struct{

DateType data[MaxSize]；

int front[2],rear[2]；

}Queue2；

对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。

int EnQueue (Queue2*Q,int i,DateType x)

{//若第i个队列不满，则元素x入队列，并返回1；否则返回0

if(i<0||i>1)return 0；

if(Q－>rear[i]==Q－>front[ ①]return0；

Q－>data[ ②]=x；

Q－>rear[i]=[ ③];

return1；

}

①

②

③

33．已知二叉树的存储结构为二叉链表，阅读下面算法。

typedef struct node {

DateType data；

Struct node * next；

}ListNode；

typedef ListNode * LinkList ；

LinkList Leafhead=NULL；

V oid Inorder (BinTree T)

{

LinkList s；

If(T){

Inorder(T－>lchild)；

If ((!T－>lchild)&&(!T－>rchild)){

s=(ListNode*)malloc(sizeof(ListNode))；

s－>data=T－>data；

s－>next=Leafhead；

Leafhead=s；

}

Inorder(T－>rchild)；

}

对于如下所示的二叉树

（1）画出执行上述算法后所建立的结构；

（2）说明该算法的功能。

五、算法设计题（本题共10分）

34．阅读下列函数arrange()

int arrange(int a[],int 1,int h,int x)

{//1和h分别为数据区的下界和上界

int i,j,t；

i=1；j=h；

while(i

while(i=x)j--；

while(i=x)i++；

if(i

{ t=a[j]；a[j]=a[i]；a[i]=t；}

}

if(a[i]

else return i－1；

}

（1）写出该函数的功能；

（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。

全国2001年10月高等教育自学考试

数据结构试题参考答案

课程代码：02331

一、单项选择题（本大题共15小题，每小题2分，共30分）

1．D ２．Ｂ３．Ｃ４．Ｂ５．Ｄ

６．Ａ７．Ｃ８，Ｄ９，Ａ10．Ｃ

11．Ｄ12．Ｃ13．Ｄ14．Ｃ15．Ｂ

二、填空题（本大题共10小题，每小题2分，共20分）

16．存储（或存储结构）17.p－＞next－＞next

18．进栈和退栈19．12

20．a4,8 21．384

22．abefcdg 23．快速排序、堆排序、希尔排序

24．２25.多关键字

三、解答题（本大题共4小题，每小题5分，共20分）

26．

图1 图2

27．

28．该图的图形为：

深度优先遍历序列为：abdce 广度优先遍历序列为：abedc 29．（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１；（２）平均查找长度ASL =

++++=3211259

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30． ①S1=S1－>next ②s2=s2－>next

③s2(或s2!=NULL 或s2&&!s1) ④s1(或s1!=NULL 或s1&&!s2) ⑤return 0

31.（1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a 2,a 3,…,a n ,a 1） 32. ①(i ＋1)%2(或1－i) ②Q －>rear[i]

③(Q －

33.(1)Leafhead

（2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead 为头

指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。

五、算法设计题（本题共10分） 34．（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i ，使所有＜x 的元

素均落在a[1..i]上，使所有≥x 的元素均落在a[i ＋1..h]上。

（2）int f(int b[],int n) 或int f(int b[],int n)

{ {

int p,q；int p,q；

p=arrange(b,0,n－1,0)；p=arrange(b,0,n－1,1)；

q= arrange(b,p+1,n－1,1)；q= arrange(b,0,p,0)；

return q－p；return p－q；

} }

2003.1数据结构试题

一、单项选择题(本大题共15小题，每小题2分，共30分。在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内)

1.下面程序段的时间复杂度是( D )

for(i=0;i<n;i++)

for(j=1;j<m;j++)

A[i][j]=0；

A.O(n)

B.O(m+n+1)

C.O(m+n)

D.O(m*n)

2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( B )

A.p=p->next;

B.p->next=p->next->next;

C.p->next=p;

D.p=p->next->next;

3.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则( D )

A.p指向头结点

B.p指向尾结点

C.*p的直接后继是头结点

D.*P的直接后继是尾结点

4.判定“带头结点的链队列为空”的条件是( C )

A.Q.front==NULL

B.Q.rear==NULL

C.Q.front==Q.rear

D.Q.front!=Q.rear

5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( D )

A.联接

B.求子串

C.字符定位

D.子串定位

6.广义表A=(a,(b),(),(c,d,e))的长度为( A )

A.4

B.5

C.6

D.7

7.一棵含18个结点的二叉树的高度至少为( C )

A.3

B.4

C.5

D.6

8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( D )

A.DEBAFC

B.DEFBCA

C.DEBCFA

D.DEBFCA

9.无向图中一个顶点的度是指图中( B )

A.通过该顶点的简单路径数

B.与该顶点相邻接的顶点数

C.通过该顶点的回路数

D.与该顶点连通的顶点数

10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( C )

A.a c e f b d

B.a c b d f e

C.a c b d e f

D.a c d b f e

11.在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是( B )

A.快速排序

B.堆排序

C.归并排序

D.基数排序

12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( A )

A.{25,36,48,72,23,40,79,82,16,35}

B.{25,36,48,72,16,23,40,79,82,35}

C.{25,36,48,72,16,23,35,40,79,82}

D.{16,23,25,35,36,40,48,72,79,82}

13.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( B )

A.21

B.23

C.41

D.62

14.索引非顺序文件的特点是( A )

A.主文件无序，索引表有序

B.主文件有序，索引表无序

C.主文件有序，索引表有序

D.主文件无序，索引表无序

15.倒排文件的主要优点是( C )

A.便于进行插入和删除运算

B.便于进行文件的恢复

C.便于进行多关键字查询

D.节省存储空间

二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)

16.抽象数据类型的特点是将___数据_____和____运算____封装在一起，从而现实信息隐藏。

17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需___前移___一个位置。

18.在队列中，允许进行插入操作的一端称为____队尾____，允许进行删除操作的一端称为___队头___。

19.如图两个栈共享一个向量空间，top1和top2分别为指向两个栈顶元素的指针，则“栈满”

的判定条件是__top1=top2-1____。

20.设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是_ good book__。

21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为

100，则元素A[9][8][7]的存储地址是__2257_____。

22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为__（(n-1)/k）*(k-1)+1_或n - (n-1)/k__。

23.能够成功完全拓扑排序的图一定是一个__有向无环图__。

24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用__堆排序__较为适当。

25.假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为__hi=(H(key)+I)/m___。

三、解答题(本大题共4小题，每小题5分，共20分)

26.假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。

27.已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd，进行广度优先遍历时得到的顶点序列为acbdfe。

答案：

28.已知两个4×5的稀疏矩阵的三元组表分别如下：

0 1 4 16 0 1 1 32

1 2 2 18 1 2 2 －22

2 3 4 －25 2 2 5 69

3 4 2 28 3 3 4 25

4 4 2 51

请画出这两个稀疏矩阵之和的三元组表。

解:

29.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。

(1)画出该二叉排序树

(2)画出删去该树中元素值为90的结点之后的二叉排序树。

四、算法阅读题(本大题共4小题，每小题5分，共20分)

30.如图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：

typedef struct {

DataType data[MaxSize];

int front[2],length[2];

} Queue2;

对于i=0或1,front[i]和length[i]分别为第i个队列的头指针和长度域。请在空缺处填入合适的内容，实现第i个循环队列的入队操作。

int EnQueue(Queue2*Q,int i,DataType x)

{//若第i个队列不满，则元素x入队列，并返回1，否则返回0

if(i<0||i>1)return 0;

if( (1) )

return 0;

Q->data[ (2) ]=x;

Q->length[ (3) ]++;

return 1;

}

解:

(1) (Q->front[i]+Q->length[i]%Maxsize==Q->front[(i+1)%2]

(2) (Q->front[i]+->length[i]%Maxsize

(3) I

31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。

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

(1)写出执行函数调用f(p)的输出结果；

(2)简述函数f的功能。

void f(BinThrTree t)

{

while(t)

{

printf(t->data);

if(t->lchild)

t=t->lchild;

else

t=t->rchild;

}

答案（1）ABDFCEGH (2) 先根遍历

32.下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点vi的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点vk的下一个顶点是vj。

请在空缺处填入合适的内容，使其成为一个完整的算法。

vertex firstedge

已知邻接表的顶点表结点结构为：

adjvex next

边表结点EdgeNode结构为：

int cycle_path[MaxNum];

int FindCycle(ALGraph*G,int i)

{//若回路存在，则返回1，否则返回0

int j;

for(j=0;j<G->n;j++)cycle_path[j]=-1;

return DFSPath(G,i,i);

}

int DFSPath(ALGraph*G,int j,int i)

{

EdgeNode *p;

int cycled=0;

for(p=G->adjlist[j].firstedge;p&&!cycled;p=p->next)

{

cycle_path[j]=p->adjvex;

if( (1 ) )cycled=1;//已找到回路

else

if(cycle_path[p->adjvex]==-1)cycled= (2) ;

}

return (3)

} (1) (2) (3)

32题答案：（1）p->adjvex==i

(2)DFSpath(G,p->adjvex,i)

(3)cycled

33.阅读下列函数algo,并回答问题。

(1)假设整型数组A[1..8]中的元素依次为(3，8，9，1，7，4，2，6)。执行函数调用algo(A,8)时，外层while的循环体执行多少次?函数的返回值是多少?

(2)简述函数algo(L,n)的功能。

int algo(int L[],intn)

{

int i=0,j,s=1,t=n;

while (i!=(n+1)/2)

{

int x=L[s]；

i=s;j=t;

while(i<j)

{

while(i<j && L[j]>=x)j--;

L[i]=L[j];

while(i<j && L[i]<=x)i++;

L[j]=L[i];

}

L[i]=x;

if(i<(n+1)/2)s=i+1;

else t=i-1;

}

if(i==0)return 0;

else return L[i];

} (1) (2) (3)

33题答案：

（1）外循环执行4次，函数返回值为3。

（2）将A[1]至A[8]中不小于A[1]的元素进行递增排序，如调用algo(A,8)时最终排序结果为

2 1

4 6 7 8 9

五、算法设计题(本大题共10分)

34.假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为O(n)的算法，删除表中所有数值相同的多余元素，并释放结点空间。例如：(7，10，10，21，30，42，42，42，51，70) 经算法操作后变为(7，10，21，30，42，51，70) 34题答案：

Exam4(Linklist,L)

{listnode *p,*q;

p=L->next;

while(p!=L)

{q=p->next;

while(q&&q->data==p->data)

{p->next=q->next;

free(q);

q=p->next;

}

p->next;

}

2003年10月全国数据结构试题（2006-7-25 2:07:00）

1.计算机识别、存储和加工处理的对象被统称为( b )

A.数据

B.数据元素

C.数据结构

D.数据类型

2.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( b )

A.O(1)

B.O(n)

C.O(nlogn)

D.O(n2)

3.队和栈的主要区别是( d )

A.逻辑结构不同

B.存储结构不同

C.所包含的运算个数不同

D.限定插入和删除的位置不同

4.链栈与顺序栈相比，比较明显的优点是( d )

A.插入操作更加方便

B.删除操作更加方便

C.不会出现下溢的情况

D.不会出现上溢的情况

5.采用两类不同存储结构的字符串可分别简称为( b )

A.主串和子串

B.顺序串和链串

C.目标串和模式串

D.变量串和常量串

6.在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是( c )

A.0

B.2

C.3

D.5

7.已知广义表的表头为a，表尾为(b,c)，则此广义表为( b )

A.(a,(b,c))

B.(a,b,c)

C.((a),b,c)

D.((a,b,c))

8.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为( c )

A.470

B.471

C.472

D.473

9.二叉树中第5层上的结点个数最多为( d )

A.8

B.15

C.16

D.32

10.下列编码中属前缀码的是( a )

A.{1,01,000,001}

B.{1,01,011,010}

C.{0,10,110,11}

D.{0,1,00,11}

11.如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是( d )

A.有向完全图

B.连通图

C.强连通图

D.有向无环图

12.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( d )

A.O(1)

B.O(logn)

C.O(n)

D.O(n logn)

13.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( n/2 )

A. B.

C. D.n

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

A.35和41

B.23和39

C.15和44

D.25和51

15.稠密索引是在索引表中( )

A.为每个记录建立一个索引项

B.为每个页块建立一个索引项

C.为每组记录建立一个索引项

D.为每个字段建立一个索引项

二、填空题（每小题2分，若有两个空格，每个空格1分，共20分）

16.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的__(_时间复杂度_) ____。

17.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作_(存储密度)___ ____。

date next

18.已知链栈的结点结构为栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为________和________。

19.空串的长度是___0_____；空格串的长度是____(空格的数目_)___。

20.假设一个6阶的下三角矩阵B按列优先顺序压缩存储在一维数组A中，其中A［0］存储矩阵的第一个元素b11,则A［14］存储的元素是______b63__。

21.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是____2____。

22.如图所示的有向无环图可以排出________种不同的拓扑序列。

23.利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(___75,66,48,29,31,3 7_____)。

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

25.在多重表文件中，次关键字索引的组织方式是将________的记录链接成一个链表。

26.对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。

date next

单链表和单循环链表的结点结构为

prior date next

双向链表的结点结构为

(1)单链表: (不可以,无法找到前驱接点)

(2)单循环链表(可以:q=p->next;while(q->next!=p)q=q->next;q->data<->p->data;

(3)双向链表(可以:p->prior->data<->p->data;)

27.假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。

(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；

(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。

28.当采用邻接表作为图的存储结构时，也可将邻接表中的顶点表由顺序结构改为链表结构。

(1)请分别画出这种邻接表的顶点链表结点和边表结点，并说明结点中各个域的作用；

(2)对如图所示的有向图画出这种邻接表。

29.已知4阶B-树如图所示。

(1)分别画出将关键字23和89相继插入之后的B-树。

(2)画出从插入之前的B-树中删除关键字51之后的B-树。

四、算法阅读题(每小题5分，共20分)

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

(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q；

(2)简述算法algo的功能。

void algo(Queue *Q)

{

Stack S;

InitStack(&S);

while (!QueueEmpty(Q))

Push(&S, DeQueue(Q));

while (! StackEmpty(&S))

ＥnQueue(Q,Pop(&S));

}

(1)87542

(2) 队列倒置

31.阅读下列函数F，并回答问题：

(1)已知如图所示的二叉树以二叉链表作存储结构，rt为指向根结点的指针。写出执行函数调用F(rt)的输出结果。

(2)说明函数F的功能。

void F(BinTree T)

{

Stack S;

if(T)

{

InitStack(&S);

Push(&S,NULL);

while(T)

{

printf("%c", T->data);

if(T->rchild) Push(&S,T->rchild);

if(T->lchild)T=T->lchild;

else T=Pop(&S);

}

(1)

(2)前序遍历二叉数

vertex firstedge

32.已知邻接表的顶点表结点结构为

adjvex next

边表结点EdgeNode的结构为

下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。

int FindDegree(ALGraph *G,int i)//ALGraph为图的邻接表类型

{

int dgree, j;

EdgeNode *p;

degree= (1) ;

for(j=0;jn;j++)

{

p=G->adjlist［j］. firstedge;

while ( (2) )

{

if( (3) )

{

degree++;

break;

}

p=p->next;

}

return degree;

}

(1)degree=0;

(2)p

(3)p->adj==vi

data next

33.已知单链表的结点结构为

下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。

请在空缺处填入合适的内容，使其成为完整的算法。

void SelectSort(LinkedList L)

{

LinkedList p,q,min;

DataType rcd;

p= (1) ;

while(p!=NULL) {

min=p;

q=p->next;

while(q!=NULL){

if( (2) )min=q;

q=q->next;

}

if( (3) ){

rcd=p->data;

p->data=min->data;

min->data=rcd;

}

(4) ;

}

(1)L->next

(2)q->datadata

(3)p!=min

(4)p=p->next

五、算法设计题(本题10分)

34.设线性表A=(a1,a2,a3,…,an)以带头结点的单链表作为存储结构。编写一个函数，对A进行调整，使得当n为奇数时A=(a2,a4,…,an-1,a1,a3,…,an)，当n为偶数时A=(a2,a4,…,an,a1, a3,…,an-1)。

typedef struct node

{

int x;

struct node *next;

} NODE;

typedef NODE * LinkList;

void adjust( LinkList header )

{

NODE *pTmp = header; //用来保存偶数链表尾指针

NODE *pCur = header->next; //链表遍历指针

NODE *pOddHdr = header->next;//奇数链表头指针

NODE *pOddTail = header->next;//奇数链表尾指针

int bIsOdd = true; //奇数结点标志，第一个结点是奇数结点

if( NULL == pCur )//空链表，不需要处理

return;

while( pCur->next != NULL )//从第二个结点开始遍历

{

pCur = pCur->next;

bIsOdd = !bIsOdd;

if( bIsOdd ) //（这步错误，未将原链表的接点连接）

{//奇数结点，加入奇数链表表尾

pOddTail->next = pCur;

pOddTail = pCur;

}

else

{//偶数结点，加入偶数链表表尾

pTmp->next = pCur;

pTmp = pCur;

}

pOddTail->next = NULL;//奇数链表表尾结点的next置空

pTmp->next = pOddHdr;//奇数链表插入偶数链表表尾（这步错误，未考虑最后接点的奇偶性。）

return;

}

全国2004年1月高等教育自学考试

数据结构试题

课程代码：02331

一、单项选择题（本大题共15小题，每小题2分，共30分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．在数据结构中，数据的逻辑结构可以分成（）

A．内部结构和外部结构B．线性结构和非线性结构

C．紧凑结构和非紧揍结构 D．动态结构和静态结构

2．在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）

A．数据元素的相邻地址表示 B．数据元素在表中的序号表示

C．指向后继元素的指针表示 D．数据元素的值表示

3．设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（）s -> next = p -> next; p -> next = s;

t = p -> data; p -> data = s -> data; s ->data = t;

A．结点*p与结点*s的数据域互换

数据结构-数据结构历年考题及答案2

中国矿业大学2011-2012学年《数据结构》试卷（A卷）（考试时间：100分钟）一. 填空（每空2分，共40分） 1. 数据结构式具有相同性质的数据元素的（1）。 2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。 5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。 6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。 7. 一棵二叉树为则后序序列为（12），中序序列为（13），先序序列为__（14）____。 8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。 9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。二简答题： 1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。 C G E D F B H A

计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编6

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编6 (总分：60.00，做题时间：90分钟) 一、单项选择题(总题数：14，分数：28.00) 1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。【2009年全国试题1(2)分】 A.栈 B.队列√ C.树 D.图 2.设栈S和队列Q的初始状态均为空，元素a，b，c，d,e,j,g=g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是( )。【2009年全国试题2(2)分】 A.1 B.2 C.3 √ D.4 按元素出队顺序计算栈的容量。b进栈时栈中有a，b出栈，cd进栈，栈中有acd，dc出栈，ef进栈，栈中有aef,fea出栈，栈空，g进栈后出栈。所以栈S的容量至少是3。 3.若元素a，b，c，d,e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。【2010年全国试题1(2)分】 A.d,c，e，b，f,a B.c，b，d,a，e，f C.b，c，a，e，f，d D.a,f，e,d,c，b √ 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。【2010年全国试题2(2)分】 A.b，a，c，d, e B.d,b，a，c，e C.d，b,c，a，e √ D.e，c，b，a，d a先入队，b和c可在a的任一端入队，选项A、B、D都符合要求，只有选项C不可能出现。双端队列出队结果的分析可参见四、36。 5.元素a，b，c，d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是( )。【2011年全国试题2(2)分】 A.3 B.4 √ C.5 D.6 元素d进栈时，元素a，b，c已在栈中，d出栈后，P可以在a，b，c任一元素的前面进栈并出栈，也可以在元素a后出栈，c，b，a必须依次出栈，所以元素d开头的序列个数是4。 6.已知循环队列存储在一维数组A[0．n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是( )。[2011年全国试题3(2)分】 A.0，0 B.0，n—1 √ C.n一1，0

计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编6

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 6 (总分：88.00，做题时间：90分钟) 一、单项选择题(总题数：33，分数：66.00) 1.一棵完全二叉树又是一棵( )。【华中科技大学2006一、7(2分)】 A.平衡二叉树 B.堆√ C.二叉排序树 D.哈夫曼(Huffman)树完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。 2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学1999一、5(2分)】 A.不确定 B.0 C.1 D.2 √ 左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。 3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学2000一、5(2分)】 A.0 B.1 √ C.2 D.不确定 4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。【南京理工大学1996 一、6(2分)】 A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点√ D.X的左子树中最右叶结点 5.引入二叉线索树的目的是( )。【南京理工大学1998一、5(2分)】 A.加快查找结点的前驱或后继的速度√ B.为了能在二叉树中方便地进行插入与删除 C.为了能方便地找到双亲 D.使二叉树的遍历结果唯一 6.线素二叉树是一种( )结构。【西安电子科技大学1996一、9(2分)】 A.逻辑 B.逻辑和存储 C.物理√ D.线性 7.甩个结点的线索二叉树上含有的线索数为( )。【中山大学1998二、8(2分)】

数据结构历年真题收集第1章绪论(含答案)

第1章绪论一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1]

计算机专业基础综合数据结构(概论)历年真题试卷汇编3

计算机专业基础综合数据结构（概论）历年真题试卷汇编3 (总分：70.00，做题时间：90分钟) 一、单项选择题(总题数：15，分数：30.00) 1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。【2011年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1年全国试题1(2分)】 x=2； while(x *x；（分数：2.00） A.O(log 2 n) √ B.O(n) C.O(nlog 2 n) D.O(n 2 ) 解析： 2.求整数n(n≥0)阶乘的算法如下，其时间复杂度是( )。【2012年全国试题1(2分)】int fact(int n){if(n<=i) return i；return n*fact(n一1)；（分数：2.00） A.O(log 2 n) B.O(n) √ C.O(nlog 2 n) D.O(n 2 ) 解析： 3.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是( )。【2013年全国试题1(2)分】（分数：2.00） A.O(n) B.O(m×n) C.O(min(m，n)) D.O(max(m，n)) √ 解析： 4.下列程序段的时间复杂度是( )。【2014年全国试题1(2分)】count=0;for(k=1；k<=n；k*=2)for(j=1；j<=n；j++)count++；（分数：2.00） A.O(log 2 n) B.O(n) C.O(nlog 2 n) √ D.O(n 2 ) 解析： 5.在数据结构中，数据的最小单位是( )。【北京理工大学2006九、1(1分)】（分数：2.00） A.数据元素 B.字节 C.数据项√ D.结点解析： 6.在数据结构中，数据的基本单位是( )。【北京理工大学2004五、1(1分)】（分数：2.00） A.数据项 B.数据类型 C.数据元素√

计算机考研数据结构统考历年真题

目前刚整理了2009-2015的试题过几天2016的也会上传上去希望对你有帮助。。。。。。。 2009 1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 A.栈 B.队列 C.树 D.图 2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是 A．1 B.2 C.3 D.4 3.给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是 A．LRN B.NRL C.RLN D.RNL 4.下列二叉排序树中，满足平衡二叉树定义的是 5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是 A．39 B.52 C.111 D.119 6.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的

父结点，则在原来的森林中，u和v可能具有的关系是I．父子关系 II.兄弟关系 III.u的父结点与v的父结点是兄弟关系 A.只有II B.I和II C.I和III D.I、II和III 7.下列关于无向连通图特性的叙述中，正确的是 I．所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1 A.只有I B.只有II C.I和II D.I和III 8.下列叙述中，不符合m阶B树定义要求的是 A．根节点最多有m棵子树 B.所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接 9.已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是 A．3，5，12，8，28，20，15，22，19 B.3，5，12，19，20，15，22，8，28 C．3，8，12，5，20，15，22，28，19 D.3，12，5，8，28，20，15，22，19 10.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是 A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序 41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：

计算机专业基础综合数据结构(图)历年真题试卷汇编3

计算机专业基础综合数据结构（图）历年真题试卷汇编3 (总分：58.00，做题时间：90分钟) 一、综合题(总题数：23，分数：58.00) 1.给出从顶点v1开始，对图G用深度优先搜索法进行遍历时的顶点序列；(2)给出从顶v1，1开始，对图G用广度优先搜索法进行遍历时的顶点序列。【复旦大学1998六(10分)】 __________________________________________________________________________________________ 正确答案：(正确答案：(1)v 1 v 2 v 4 v 3 v 5 v 6 (2) v 1 v 2 v 3 v 4 v 5 v 6) 给出图G 4.00） (1).画出G的邻接表表示图； __________________________________________________________________________________________ 正确答案：( (2).根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。【南开大学1997五(14分)】【烟台大学2007四、3(15分)】 __________________________________________________________________________________________ 正确答案：( 2.已知一个有向图如图所示，则从顶点a出发进行深度优先遍历，写出所有可能得到的DFS 京交通大学2006四、4(5分)】 __________________________________________________________________________________________ 正确答案：(正确答案：共8个：adbcfe，adbfce，adcbfe，adcebf adcefb，adebcj,adebfc，adefbc) 2000计算机应用六(10分)】（分数：4.00） (1).如果每个指针需要4字节，每个顶点的标号占2字节，每条边的权值占2字节。下图采用哪种表示法所需的空间较多?为什么? __________________________________________________________________________________________ 正确答案：(正确答案：邻接矩阵：(6*6个元素)*2字节／元素=72字节邻接表：表头向量6*(4+2)+边结点9*(2+2+4)*2=180字节邻接多重表：表头向量6*(4+2)+边结点9*(2+2+2+4+4)=162字节邻接表占用空间较多，因为边较多，边结点又是边数的2倍，一般来说，邻接矩阵所占空间与边个数无关(不考虑压缩存储)，适合存储稠密图，而邻接表适合存储稀疏图。邻接多重表边结点个数等于边数，但结点中增加了一个顶点下标域和一个指针域。) (2).写出下图从顶点1开始的：DFS树。 __________________________________________________________________________________________ 正确答案：(正确答案：因未确定存储结构，从顶点1开始的DFS 3.如下所示的连通图，请画出：(1)以顶点①为根的深度优先生成树；(5分)(2)如果有关节顶点，请找出所有的关节顶点。(5分)【清华大学l 998七(10分)】 __________________________________________________________________________________________ 正确答案：(正确答案：(1)未确定存储结构，其DFS树不唯一，其中之一(按邻接点逆序排列) 关节顶点有3，1，8，7，2。)

全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构考点归纳与典型题(含历年真题)详解-第一章

第1章绪论 1.1考点归纳【考纲指定考点】本章初步了解数据结构的基本概念。分析算法的时间复杂度和空间复杂度是本章的重点。一、数据结构的基本概念 1．基础概念和术语（1）数据（Data）：数据是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。（2）数据元素（Data Element）：数据元素是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。（3）数据项（Data Item）：数据项是数据的不可分割的最小单位，数据项是对客观事物的某一方面的数据描述。一个数据元素可由若干个数据项（Data Item）组成。（4）数据对象（Data Object）：数据对象是性质相同的数据元素的集合，是数据的一个子集。如字符集合C＝{‘A’，‘B’，‘C’，…}。（5）数据结构（Data Structure）：数据结构是指相互之间存在一定联系（关系）的数据元素的集合。元素之间的相互联系（关系）称为逻辑结构。 2．数据结构的形式定义

数据结构的形式定义是一个二元组： Data Structure＝（D，S）其中D是数据元素的有限集，S是D上关系的有限集。数据元素之间的关系可以是元素之间本身代表的某种自然关系，也可以是为了处理问题方便而人为定义的关系，这种自然或人为定义的关系称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。 3．数据结构的组成数据结构的三个组成部分：（1）逻辑结构数据元素之间的逻辑关系的描述。数据元素之间的逻辑结构有四种基本类型： ①集合：结构中的数据除了“同属于一个集合”外，没有其它关系。 ②线性结构：结构中的数据元素之间存在一对一的关系。 ③树形结构：结构中的数据元素之间存在一对多的关系。 ④图形结构或网状结构：结构中的数据元素之间存在多对多的关系。（2）存储结构数据结构在计算机中的实际表达方式，它包括对数据元素的表示和对关系的表示。存储结构主要有：顺序存储、链式存储、索引存储和散列存储。 ①顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构。数据元素存放的地址是连续的。其优点是可以实现随机存取，存储空间小；缺点是只能使用相邻的一整块存储单元，容易产生碎片。 ②链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针，用该指针

数据结构历年试题及答案

一、单项选择题 1．算法指的是（ D ） D ．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ B ）B ．连续与否均可 3．将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为（ C ） A ．O （1） B ．O （n ） C ．O （m ） D ．O （m+n ） 4．由两个栈共享一个向量空间的好处是：（ B ） B ．节省存储空间，降低上溢发生的机率 5．设数组data[m]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为（ D ） D ．front=(front+1)%m 6．如下陈述中正确的是（ A ） A ．串是一种特殊的线性表 7．若目标串的长度为n ，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ C ） C ．O （n 2） 8．一个非空广义表的表头（ D ） D ．可以是子表或原子 9 对应的稀疏矩阵是（ A ） ????????????? ???--0000040 5000000076080.A 10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( C ) C ．6 11．在含n 个顶点和e 条边的无向图的邻接矩阵中,零元素的个数为( D ) D ．n 2－2e 12．假设一个有n 个顶点和e 条弧的有向图用邻接表表示,则删除与某个顶点v i 相关的所有弧的时间复杂度是( C ) C ．O(n+e) 13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ D ） D ．快速排序 14．适于对动态查找表进行高效率查找的组织结构是（ C ） C ．三叉排序树 15．不定长文件是指（B ） B ．记录的长度不固定二、填空题 16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储（存储结构）无关，是独立于计算机的。 17．在一个带头结点的单循环链表中，p 指向尾结点的直接前驱，则指向头结点的指针head 可用p 表示为head= p->next->next 。 18．栈顶的位置是随着进栈和退栈操作而变化的。 19．在串S=“structure ”中，以t 为首字符的子串有 12 个。

第一部分“数据结构”历年真题

第一部分“数据结构”历年真题一、选择题 1、(05-9-2)下列数据结构中，能用二分法进行查找的是（） A）顺序存储的有序线性表B）线性链表 C）二叉链表D）有序线性链表 2、(05-9-3)下列关于栈的描述正确的是（） A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素 3、(05-9-4)下列叙述正确的是（） A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 4、(08-9-3)在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（） A）O(N) B）O(n2) C）O(log2n)D）O(n log2n) 5、(06-4-4)按照“后进先出”的原则组织数据的数据结构是 A）队列B）栈C）双向链表D）二叉树 6、(06-4-5)下列叙述中正确的是（） A）线性链表是线性表的链式存储结构B）栈与队列是非线性结构 C）双向链表是非线性结构D）只有根结点的二叉树是线性结构 7、(06-4-6)对如下二叉树进行后序遍历的结果为（） A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA 8、(06-4-7)在深度为7的满二叉树中，叶子结点的个数为（）

A ）32 B ）31 C ）64 D ）63 9、(06-9-7)下列叙述中正确的是（） A ）一个算法的空间复杂度大，则其时间复杂度也必定大 B ）一个算法的空间复杂度大，则其时间复杂度必定小 C ）一个算法的时间复杂度大，则其空间复杂度必定小 D ）上述三种说法都不对 10、(06-9-8)在长度为64的有序线型表中进行顺序查找，最坏情况下需要比较的次数为（） A ）63 B ）64 C ）6 D ）7 11、(06-9-10) 进行中序遍历的结果是（） A ）ACBDFEG B ）ACBDFGE C ） ABDCGEF D ）FCADBEG 12、(07-4-1)下列叙述中正确的是（） A ）算法的效率只与问题的规模有关，而与数据的存储结构无关 B ）算法的时间复杂度是指执行算法所需要的计算工作量 C ）数据的逻辑结构与存储结构是一一对应的 D ）算法的时间复杂度与空间复杂度一定相关 13、(07-4-5)下列对队列的叙述正确的是（） A ）队列属于非线性表 B ）队列按“先进后出”原则组织数据 C ）队列在队尾删除数据 D ）队列按“先进先出”原则组织数据 14、(07-4-6)对下列二叉树

计算机专业基础综合数据结构(排序)历年真题试卷汇编5

计算机专业基础综合数据结构（排序）历年真题试卷汇编5 (总分：66.00，做题时间：90分钟) 一、单项选择题(总题数：15，分数：30.00) 1.已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。【2009年全国试题9(2分)】 A.3，5，12，8，28，20，15，22，19 √ B.3，5，12，19，20，1 5，22，8，28 C.3，8，12，5，20，15，22，28，19 D.3，12，5，8，28，20，1 5，22，19 首先按所给关键字序列画出完全二叉树，关键字3插入结点22的后边。沿结点3到根的路径调整堆，直到满足堆的定义为止。 2.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )。【2009年全国试题10(2分)】 A.起泡排序 B.插入排序√ C.选择排序 D.二路归并排序起泡排序的特点是待排序元素相邻两两比较，逆序交换，每趟有一个最大元素到达底部(或一个最小元素到达顶部)；插入排序的特点是先假定第一个元素有序，从第二个元素起，每趟将未排序元素的第一个元素插入的前面有序子文件中；选择排序的特点是第一趟在待排序元素中选最小(或最大)元素和第一个元素交换，第二趟在未排序元素中选次小(或次大)和第二个元素交换；二路归并排序是两两归并，再四四归并，等等。 3.采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是( )。【2010年全国试题10(2分)】 A.递归次数与初始数据的排列次序无关 B.每次划分后，先处理较长的分区可以减少递归次数 C.每次划分后，先处理较短的分区可以减少递归次数 D.递归次数与每次划分后得到的分区的处理顺序无关√ 快速排序和数据的初始排列次序相关。每次划分后，先处理较短分区可以减少递归深度，递归次数和先处理哪个分区无关。 4.对一组数据(2，12，1 6，88，5，10)进行排序，若前三趟排序结果如下：第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88则采用的排序方法可能是( )。【2010年全国试题11(2分)】 A.起泡排序√ B.希尔排序 C.归并排序 D.基数排序起泡排序和二路归并排序的特点见上面第2题。希尔排序是先按步长分组，组内进行插入排序，逐渐减少步长，最后步长为1进行一趟直接插入排序。根据各种排序的特点，可以分析出本题是起泡排序。 5.为实现快速排序算法，待排序序列宜采用的存储方式是( )。【2011年全国试题10(2分)】 A.顺序存储√ B.散列存储 C.链式存储 D.索引存储每趟排序结束时都至少能够确定一个元素最终位置的排序方法有起泡排序、快速排序、简单选择排序、堆排序。 6.已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是( )。【2011年全国试题11(2分)】

数据结构历年试题及答案

试卷代号：1252 中央广播电视大学2012-2013学年度第二学期“开放本科”期末考试一、单项选择题（每小题2分，共30分） 1．在C语言中，顺序存储长度为3的字符串，需要占用( )个字节。 A．4 B．3 C．6 D．12 2。串函数StrCat(a，b)的功能是进行串( )。 A．比较 B．复制 C．赋值 D．连接 3．-棵有n个结点采用链式存储的二叉树中，共有( )个指针域为空。 A．n+l B．n C．n-l D．n-2 4．设一棵哈夫曼树共有n个非叶结点，则该树有( )个叶结点。A．n B．n+l C．n-l D．2n 5．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行( )。 A. x=top->data;top=top->next =top->data C. top= top->next; x=top->data =top->next;x=data 6．一棵完全二叉树共有5层，且第5层上有六个结点，该树共有( )个结点。 A．30 B．20 C．21 D．23 7．在一个无向图中，所有顶点的度数之和等于边数的( )倍。^A．O上；．B．3 C． D．2 8．已知如图1所示的一个图，若从顶点V，出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。 9．已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。A. abcedf B. abcefd C. aebcfd D. acfdeb 10.对二叉排序树进行( )遍历，可以使遍历所得到的序列是有序序列。 A．按层次 B．后序 C．中序 D．前序 11．在有序表(2，4，7，14，34，43，47，64，75，80，90，97，120)中，用折半查找法查找值80时，经( )次比较后查找成功。 A．4 B．2 C．3 D．5

历年《数据结构》考研真题及解答

《数据结构》考研真题及解答

目录 2009 年试题 (1) 填空题 (1) 解答题 (2) 2010 年试题 (2) 填空题 (2) 解答题 (4) 2011 年试题 (4) 填空题 (4) 解答题 (5) 2012 年试题 (6) 填空题 (6) 解答题 (7) 2013 年试题 (8) 填空题 (8) 解答题 (9) 2014 年试题 (10) 填空题 (10) 解答题 (11) 2015 年试题 (12) 填空题 (12) 解答题 (14)

2009 年试题填空题 1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 A.栈 B.队列 C.树 D.图 2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是 A．1 B.2 C.3 D.4 3.给定二叉树图所示。设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是 A．LRN B.NRL C.RLN D.RNL 4.下列二叉排序树中，满足平衡二叉树定义的是 5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是 A．39 B.52 C.111 D.119 6.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系 A.只有II B.I 和II C.I 和III D.I、II 和III 7.下列关于无向连通图特性的叙述中，正确的是 I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1

哈尔滨工业大学数据结构与算法历年考题汇总

[期末] 2005数据结构与算法试卷试卷类型: 期末试卷年份: 05 授课教师: 廖明宏有无答案: 无答案哈工大2005年春季学期数据结构与算法试卷一．填空题（每空1分，共10分） 1．假定对线性表(38,25,74,52,48)进行散列存储，采用H(K)=K %7作为散列函数，若分别采用线性探查法和链接法处理冲突，则对各自散列表进行查找的平均查找长度分别为_______和________。 2．假定一组记录的排序码为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为________________。 3．在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。 4．有向图的邻接矩阵表示法中某一行非0元素的个数代表该顶点的，某一列非0元素的个数是该顶点的。 5．对于下面的带权图G3，若从顶点v0出发，则按照普里姆（Prim）算法生成的最小生成树中，依次得到的各条边为______________。 6．由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为 7．由三个结点构成的二叉树，共有种不同结构。二．选择题（每题1分，共10分） 1．快速分类在的情况下不利于发挥其长处. A. 待分类的数据量太大 B. 待分类的数据相同值过多 C. 待分类的数据已基本有序 D. 待分类的数据值差过大. 2．两路归并排序中，归并的趟数是。

A. O(n) B. O(log2n) C. O(nlog2n) D. O(n2) 注意行为规范遵守考场纪律第1页，共6页 3．对外部分类的K路平衡归并，采用败者树时，归并的效率与K 。 A. 有关 B.无关 C.不能确定 D. 都不对 4．对于一个索引顺序文件，索引表中的每个索引项对应主文件中的。 A. 一条记录 B.多条记录 C. 所有记录 D.三条以上记录 5．.若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址时。 A.112 B.144 C.148 D.412 6．若频繁地对线性表进行插入和删除操作，该线性表应该采用存储结构。 A.散列 B.顺序 C.链式 D.索引 7．若长度为n的非空线性表采用顺序储存结构，删除表中第i个数据元素，需要移动表中个数据元素。 A.n+i B.n-i C.n-i+1 D.n-i-1 8．栈和队列的相同之处是。 A.元素的进出满足先进后出 B.元素的进出满足后进先出 C.只允许在端点进行插入和删除操作 D.无共同点 9．在一棵高度为k的二叉树中，最多含有( )个结点。 A．2k-1 B．2k-l C．2k-1 D．k

武汉理工大学历年数据结构试题及答案修改一

数据结构试卷（一）一、单选题（每题 2 分，共20分） 1.栈和队列的共同特点是( A )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). k-1 A．2k-1 B.2K+1 C.2K-1 D. 2 7.若有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（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：__ _、__ _____、______和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_____。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_____个，树的深度为______，树的度为____。 4.后缀算式9 2 3 +- 10 2 / -的值为______。中缀算式（3+4X）-2Y/3对应的后缀算式为 _______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存

燕山大学操作系统与数据结构历年考研真题答案附后

燕山大学操作系统与数据结构历年考研真题答案附后最新资料，WORD格式，可编辑修改！目录

1．燕山大学操作系统与数据结构历年考研真题 (3) 2015年燕山大学810操作系统与数据结构考研真题 (3) 2014年燕山大学811操作系统与数据结构考研真题 (9) 2013年燕山大学810操作系统与数据结构考研真题 (15) 2012年燕山大学810操作系统与数据结构考研真题 (21) 2．中国计量学院数据结构与操作系统历年考研真题 (27) 2015年中国计量学院806数据结构与操作系统考研真题 (27) 2014年中国计量学院818数据结构与操作系统考研真题 (37) 2013年中国计量学院818数据结构与操作系统考研真题 (46) 3．广东工业大学操作系统历年考研真题 (56) 2014年广东工业大学830操作系统考研真题 (56) 2013年广东工业大学830操作系统考研真题 (64) 4．沈阳航空航天大学操作系统历年考研真题 (72) 2014年沈阳航空航天大学811操作系统考研真题 (72) 2013年沈阳航空航天大学811操作系统考研真题 (76) 5．沈阳工业大学计算机操作系统历年考研真题 (82) 2014年沈阳工业大学837计算机操作系统考研真题 (82) 2013年沈阳工业大学837计算机操作系统考研真题 .................. 错误!未定义书签。6．山东科技大学数据结构与操作系统历年考研真题. (90) 2014年山东科技大学830数据结构与操作系统考研真题 (90) 2012年山东科技大学838数据结构与操作系统考研真题 (94) 2011年山东科技大学827数据结构与操作系统考研真题 (96) 说明：精选了16套名校操作系统历年考研真题

文档之家

自考数据结构历年试题及答案

数据结构-数据结构历年考题及答案2

计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编6

计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编6

数据结构历年真题收集第1章 绪论(含答案)

计算机专业基础综合数据结构(概论)历年真题试卷汇编3

计算机考研数据结构统考历年真题

计算机专业基础综合数据结构(图)历年真题试卷汇编3

全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构考点归纳与典型题(含历年真题)详解-第一章

数据结构历年试题及答案

第一部分“数据结构”历年真题

计算机专业基础综合数据结构(排序)历年真题试卷汇编5

数据结构历年试题及答案

历年《数据结构》考研真题及解答

哈尔滨工业大学数据结构与算法历年考题汇总

武汉理工大学历年数据结构试题及答案修改一

最新海南大学数据结构往年试题

燕山大学操作系统与数据结构历年考研真题答案附后

数据结构历年真题收集第1章绪论(含答案)