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

第一部分 选择题(30分)

一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只

有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

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

时间复杂度是（ ） A．O（） B．O（n） C．O（n2） D．O（n3） 9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表

0 2 3 3 5 对应的稀疏矩阵是（ ） ?0?8?70? A.?00???50??00?0?8?00? C.?02???50??0006??0?8?7000????00 B.??50??40??00?00?3??006?00??40?

?00?00??n3?0?8006??00000???0000? D.?7??40???50400????0306?0??0? ?0?0??12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有

弧的时间复杂度是( )

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 则所采用的排序方法是（ ）

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

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

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

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

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

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

21．已知一棵完全二叉树中共有768结点，则该树中共有 个叶子结点。 23．在单链表上难以实现的排序方法有 和 。 25．多重表文件和倒排文件都归属于 多关键字 文件。 三、解答题（本大题共4小题，每小题5分，共20分）

26．画出下列广义表的共享结构图形表示 P=（（（z）,(x,y)）,((x,y),x),(z)） 27．请画出与下列二叉树对应的森林。

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

a

?01001?b ?10010?? c ??00011?d ???01101?e

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

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

29．已知一个散列表如下图所示： 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12

其散列函数为h(key)=key, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+i*h1(key))%m i=0,1,?，m－1 其中

h1(key)=key+1 回答下列问题：

（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？ （2）该散列表在等概率查找时查找成功的平均查找长度为多少？ 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．下列算法的功能是比较两个链串的大小，其返回值为：

??1当s1?s2? comstr(s1,s2)=?0当s1?s2

?1当s?s12?请在空白处填入适当的内容。

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, ?,an）,写出算法执行后的返回值所表示的线性表。

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； Void 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]

（1）写出该函数的功能； （2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，

将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。

一、单项选择题（本大题共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?3?2?1?1?29?

55四、算法阅读题（本大题共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）返回的线性表为（a2,a3,?,an,a1） 32. ①(i＋1)%2(或1－i) ②Q－>rear[i]

③(Q－>rear[i]＋)%Maxsize 33.(1)Leafhead

F H G D ∧ （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 3 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,被称为同义词的关键字是( 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,37_____)。

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)对如图所示的有向图画出这种邻接表。

16．下列程序段的时间复杂度为_O(n^2)_ product = 1;

for (i = n;i>0; i--) for (j = i+1; j

17．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是________________。 删除*P的直接后继结点

18．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为________________，不可能得到的出栈序列为________________ 1)cbad, cbda, cdba 2)cabd, cadb, cdab

19．若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为________________。 2 / ( 4 + 2 ) = 1/3

20．右图表示的广义表为________________。[img]/0046615335847449.jpg[img]

21．若一棵满三叉树中含有121个结点，则该 树的深度为________________。

5 // ( 3^5 - 1 ) / ( 3 - 1 ) = 121 22．若以邻接矩阵表示有向图，则邻接矩阵上

第i行中非零元素的个数即为顶点vi的________________。 出度

23．若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用________________排序方法。

24．在含20个关键字的3阶B树（2－3树）上查找一个关键字，至多需要访问___________次外存。

25．文件上的两类主要操作为________________和________________。 检索 和 维护

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

26．设栈S1的入栈序列为1 2 3 4（每个数字为13个元素），则不可能得到出栈序列3142。但可通过增设栈S2来实现。例如，按下图中的箭头指示，依次经过栈S1和S2，便可得到序列3 1 4 2。

http://www.ezikao.com.cn/uploadimages/2

( ( e ), ( ( e ), ( b, c ) ), ( L ) )

如果用H1和H2分别表示栈S1和S2的进栈操作，用P1和P2分别表示两个栈的出栈操作，则得到3 1 4 2的一个操作步骤为

H1，H1，H1，P1，H2，P2，P1，H2，P1，H2，P2，H1，P1，H2，P2，P2 请仿照上例写出利用两个栈从1 2 3 4得到4 1 3 2的操作步骤。 H1,P1,H2,H1,H1,H1,P1,H2,P2,P2,P1,H2,P2,P1,H2,P2

27．已知树如右图所示，（1）写出该树的后序序列；

（2）画出由该树转换得到的二叉树。 1) EBJKFGHICDA

2) 树变二叉树:兄弟相连,保留长子的连线 . A . / . B . / \\\\ . E C . / \\\\ . F D . / \\\\ . J G . \\\\ \\\\ . K H . \\\\ . I

28．为关键字（17，33，31，40，48）构造一个长度为7的散列表，设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是

hi = (h(key) + i(key%5+1))%7 0≤i≤6 （1）画出构造所得的散列表；

（2）求出在等概率情况下查找成功时的平均查找长度。 1)

. 0 1 2 3 4 5 6 . 31 17 48 33 40

2) ( 1 + 1 + 3 + 2 + 4 ) / 5 = 11 / 5

29．已知R［1..8］中的元素依次为（12，5，9，20，6，31，24，27），写出按算法MergeSortDC 对R进行自顶向下的二路归并排序过程中，前5次调用函数Merge(R, low, mid, high)时参数 low, mid 和high的值。

void MergeSortDC (int R[], int low, int high ) {

int mid if (low

mid = (low +high)/2; MergeSortDC (R, low, mid); MergeSortDC (R, mid+1, high); Merge (R, low, mid, high); }

} // MergeSortDC （1）第一次调用时的参数值； （2）第二次调用时的参数值； （3）第三次调用时的参数值； （4）第四次调用时的参数值； （5）第五次调用时的参数值；

//此题有一定的难度,涉及到递归调用时,系统堆栈的情况 . low mid high 1) 1 1 2 2) 3 3 4 3) 1 2 4 4) 5 5 6 5) 7 7 8 6) 5 8 6 7) 1 8 4

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

30．下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。 void union (LinkList La, LinkList Lb) {

//本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkList pre = La, q; LinkList pa = La -> next;

LinkList pb = Lb -> next; free (Lb);

while (pa && pd) {

if (pa -> data data) { pre = pa; pa = pa -> next;} else if (pa -> data > pb ->data) {

(1) ; pre = pb;

pb = pb -> next;

(2) ; } else {

q = pb; pb = pb -> next; free (q); } } if (pb)

(3) ; }

(1) pre->next = pb (2) pre->next = pa (3) pre->next = pb

31．已知串的存储结构为动态存储分配的顺序串。阅读下列算法，并回答问题：

（1）写出执行函数调用 strc (s, r)的返回结果，其中s=〃aba〃, r=〃abababa〃; （2）简述函数strc的功能。

int strc (HString * sub, HString * str) {

int i=0, j, k, count =0;

while (i < str -> length – sub -> length +1) {

j=i; k=0;

while (k _{length && str -> ch[j] = =sub -> ch[k] ) {}

j++; k++; }

if (k = = sub -> length)

{count ++; i=j-sub -> length +1;} else i++; }

return count;

} (1) 3

(2) 求串str中子串sub的个数

32．下列函数MDFSForest的功能是，对一个采用邻接矩阵作存储结构的图进行深度优先搜索遍历，输出所得深度优先生成森林中各条边。请在空缺处填入合适内容，使其成为一个完整的算法。 #define MaxMun 20 //图的最大顶点数 typedef struct {

char vexs [MaxNum]; //字符类型的顶点表 int edges [MaxNum][MaxNum]; //邻接矩阵 int n, e; //图的顶点数和边数 }MGraph; //图的邻接矩阵结构描述 typedef enum {FALSE, TRUE} Boolean; Boolean visited [MaxNum];

void MDFSTree (MGraph *G, int i); void MDFSForest (MGraph *G) {

int i, k;

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

visited [i] = (1) for (k = 0; k n; k++) if (!visited [k]) MDFSTree (G,k); }

void MDFSTree (MGraph *G, int i) {

int j;

visited [i]=TRUE;

for (j=0; j n; j++) {

if ( (2) {

printf (〃<%c, %c>〃G -> vexs [i], G (3) ; } } ｝

1) FALSE //初始化,所有结点未访问

2) !visited[ j ] && G->edge[ i ][ j ] == 1 边

3) MDFSTree( G, j ) //从j结点继续,深度优先搜索

; ) -> vexs [j]); // 结点j未访问且i到j有

33.已知整形数组L［1..8］中的元素依次为（9，8，5，7，6，3，2，1），阅读下列函数，并写出执行函数调用 sort(L, 8)时，对L进行的头两趟（pass分别为0和1）处理结果。 Void sort (int R[],int n) {

int pass = 0, k, exchange, x; do {

k=pass%2+1; exchange = 0; while (k

if (R[k]>R[k+1]) {

x = R[k]; R[k] = R[k+1]; R[k+1] = x; exchange =1; } K+=2

} pass ++;

}while (exchange = = 1|| pass <=1); }

第一趟（pass = 0）: 8 9 5 7 3 6 1 2 第二趟（pass = 1）: 8 5 9 3 7 1 6 2

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

34．已知二叉排序树中结点的关键字为整数，设计递归算法按递增有序性输出树中所有大于或等于给定值x的结点，并以函数的参数返回输出的结点个数。假设以二叉链表为存储结构，其结点结构为：

void find( BT * root, int x, int * count ) {

if( !root ) return;

if( root->key >= x ){//因为是排序树,只有当key>=x时，才需要查找其左子树 if( root-> lchild ) find( root->lchild, x , count ); (*count)++;

printf(\root->key ); }

if( root-> rchild ) find( root->rchild, x, count ); }

全国2004年10月卷答案

一、单项选择题 DABAC CCBDA ABABD

// 5.可以简单的计算，空域为3->7，总共5个，对长则为21 - 5 = 16 7.c//BDBABDABDAB BDA

123失败，比较3次 BDBABDABDAB BDA

1失败，比较1次 BDBABDABDAB BDA

12失败，比较2次 BDBABDABDAB BDA

1失败，比较1次 BDBABDABDAB BDA

123成功，比较3次 10.d

A / B / | \\ C D F | E 二、填空题 16.（一组）运算 17. 直接前驱 18. SXSSXXSSXSSXXX 19. 模式匹配 20. 5n - 6

共计10次 N+2N-2+2N-4=5N-6 // n阶5对角阵

// 1 1 1 0 0 ............ // 1 1 1 1 0 ............ // 1 1 1 1 1 0 .......... // 0 1 1 1 1 1 0......... // 0 0 1 1 1 1 1 0 ...... // ....0 1 1 1 1 1 0 .... // ...................... // ...................... 21. 50

// 63 < 100 < 127, 最下一层叶子数:100 - 63 = 37 // 倒数第2层叶子数:32 - [ 37 / 2 ] = 13 []向上取整 22. 径？

23. 待排关键字（记录）？ 24. 有序的？ 25. ?

// 一些概念题，因为没书，很久没接触了，可能不准确。 三、解答题 略

28划分后左边:(55) (28) (73) (91) (37) 右边:（64），（19），（82），（46） 第一次Merge之后:(28,55)(73) (91) (37) 右边:（64），（19），（82），（46) 第二次Merge之后:(28,55)(73,91) (37) 右边:（64），（19），（82），（46) 第三次Merge之后:(28,55,73,91)(37) 右边:（64），（19），（82），（46) 第四次Merge之后:(28,37,55,73,91) 右边:（64），（19），（82），（46) 第五次Merge之后:(28,37,55,73,91) 右边:（19,64），（82), (46) 所以.....28，37，55，73，91，19，64，82，46 四、算法阅读题 30.

1) p = pre->next; 或 p = L->next; // p指向第一个结点

2) p->next = Lc->next; // 数据大于c的p结点插入Lc链表表头 3) p = pre->next; 或 p = p->next; // 下一个结点

31.此题有误，... if ((i=!t)!=0) ... 应该是 ... if( ( i = !i ) != 0 ) ... 1) 1,3,5,7,6,4,2

2) 堆栈S中的元素依次出栈，奇数次序的入栈T,偶数次序的入队Q 32.图G的邻接矩阵不对称，因此，是有向图 1) 5

2) 计算有向图G中的端点i（第i+1个端点)的度，包括出度和入度 3) O(n)

33. 此题明显有错误if( low > high )应为if( low < high ) 因为if(){...}里有while( low < high ) 1) -8, -3, -2, -1, 4, 2, 5, 7 ：-8 -3 2 -1 -2 4 5 7

2) 将数组R中的前n个数调整为所有负数在前，所有整数在后 五、算法设计题

34. 看原型，应该是要使用递归了,题目很傻地把解法都告诉我们了。 f34(BinTree T,int level,int *lmin,int *lmax) { if(T){

if( T->lchild == NULL && T->rchild == NULL ){ if( *lmin == 0 || level < *lmin ) *lmin = level; if( level > *lmax ) *lmax = level; return; }

if( T->lchild )

f34( T->lchild, level + 1, lmin, lmax ); if( T->rchlid )

f34( T->rchild, level + 1, lmin, lmax ); } }

2005.1全国卷答案(18号更新)

一、单项选择题 BDBBB ADDCA CBACC 二、填空题 16. O(n)

17. p->next && p->next->next == NULL 18. 41 19. 0?

20. 1100 + 2 * ( 4*6*7 + 3*7 + 2 ) = 1482 21. CBDA 22. n - 1

23. 3 // 56前面，比56大的数的个数 + 1

24. 表结点的个数 25. lgn 三、解答题 26.

1) ( ((a),((b),c)) ) 27.

[方法1,liangliangzai]

b个非叶子节点,有k*b个孩子, 加上根节点,节点总数: k*b + 1

节点总数 = 非叶节点 + 叶节点 = a + b 得 a = ( k - 1 )b + 1 [方法2]

设满k叉树的高度为n,则: 叶子结点数 a = k^( n - 1 )

非叶结点数 b = 1 + k + k^2 ... + k^(n-2) = [ k^(n-1) - 1 ] / ( k - 1 ) => b = ( a - 1 ) / ( k - 1 ) => a = ( k -1 )b + 1 28

. 最短路径长度 已确定点集 最短路径直接前趋 . b c d e f b c d e f . 20 60 * 10 65 ( a ) a a * a a . 20 60 * - 30 ( a e ) a a * a e . - 50 * - 30 ( a e b ) a b * a e . - 45 110 - - ( a e b f ) a f f a e . - - 85 - - ( a e b f c ) a f c a e . - - - - - ( a e b f c d ) a f c a e 所以 a -> b 20 a,b . a -> e 10 a,e . a -> f 30 a,e,f . a -> c 45 a,e,f,c . a -> d 85 a,e,f,c,d 29

48 70 33 92 24 56 12 65 48 70 56 92 24 33 12 65 48 92 56 70 24 33 12 65 92 70 56 65 24 33 12 48 四、算法阅读题

30.1) Q->rear == Q->front && tag == 1;

2) if( Q->rear == Q->front ) tag = 1; 3) Q->rear == Q->front && tag == 0;

L->length++; } }

(1) L=(3,7,11,14,15,20,51) (2) L=(4,7,14,20,51) (3) 在顺序表L中查找数x, 找到，则删除x，

没找到，则在适当的位置插入x，插入后，L依然有序. 31. 已知图的邻接表表示的形式说明如下：

#define MaxNum 50 //图的最大顶点数 typedef struct node {

int adjvex; //邻接点域 struct node *next; //链指针域 } EdgeNode; //边表结点结构描述 typedef struct {

char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 } VertexNode; //顶点表结点结构描述 typedef struct {

VertexNode adjlist［MaxNum］; //邻接表

int n, e; //图中当前的顶点数和边数

} ALGraph; //邻接表结构描述

下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。

typedef enum {FALSE, TRUE} Boolean; Boolean visited［MaxNum］; void DFSForest(ALGraph *G){ int i;

for(i=0;in;i++) visited［i］= ________(1); for(i=0;in;i++) if (!visited［i］) DFSTree(G,i); }

void DFSTree(ALGraph *G, int i) { EdgeNode *p; visited［i］=TRUE;

p=G->adjlist［i］. firstedge; while(p!=NULL){

if(!visited［p->adjvex］){

printf(″<%c,%c>″,G->adjlist［i］. vertex,

G->adjlist［p->adjvex］. vertex);

________(2) ; }

________(3) ;

} }

(1) FALSE //初始化为未访问

(2) DSFTree( G, p->adjvex ); //从相邻结点往下继续深度搜索 (3) p = p->next; //下一个未访问的相邻结点 32. 阅读下列算法，并回答问题：

(1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L； (2)写出上述函数调用过程中进行元素交换操作的总次数。 void f32(int R［］,int n){ int i,t;

for (i=0;i

t=R［R［i］］; R［R［i］］=R［i］; R［i］=t; } }

while(){}里是把R[ i ] 和 R[ R[ i ] ] 交换;

(1) L = { 0, 1, 2, 3, 4, 5, 6, 7 }; (2)5次

33. 已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点结构为： 。请在空缺处填入适当内容，使其成为一个完整算法。 void f33 (LinkList L, LinkList H［］, int m)

{//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在 int i,j; LinkList p,q; for (i=0;i

H［i］= _________(1); p=L->next; while(p) {

q=p->next; j=p->key%m; _________(2); H［j］=p; __________(3); } free(L); }

(1) NULL //初始化 (2) p->next = H[ j ] //和下面一句完成头插法

(3) p = q; //继续遍历L 五、算法设计题(本大题10分)

34. 假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType; typedef struct node { DataType data;

struct node *lchild, *rchild; //左右孩子指针 struct node *parent; //指向双亲的指针 } BinTNode;

typedef BinTNode *BinTree;

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

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

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

a)*px 有右孩子，则其右孩子为其中序序列中的后继

b)*px 无右孩子，从*px开始回溯其祖先结点，找到第1个身份为左孩子的结点， 找到，则该结点的父结点为*px的中序序列中的后继。找不到，则无后继。 2)

BinTNode * fintNext( BinTNode * px ) {

if( px-> rchild ) return px->rchild; //*px 有右孩子 BinTNode *q, *qp; q = px;

while( qp = q->parent ){ //未回溯到根结点

if( qp->lchild == q ) return qp; //找到1)b)所述结点 q = qp; //往上回溯 }

return NULL; //未找到 }

全国2006年1月高等教育自学考试 数据结构试题 课程代码：02331

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

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

1．根据数据元素的关键字直接计算出该元素存储地址的存储方法是（ D ） A．顺序存储方法 B．链式存储方法 C．索引存储方法 D．散列存储方法

2．下述程序段中语句①的频度是（ C ） s=0;

for(i=1;i

① s+=j; A． B． C． D．

3．求单链表中当前结点的后继和前驱的时间复杂度分别是（ C ） A．O（n）和O（1） B．O（1）和O（1） C．O（1）和O（n） D．O(n)和O（n）

4．非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（ A ） A．rear->next= =head B．rear->next->next= =head C．head->next= =rear D．head->next->next= =rear

5．若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（A ） A．栈 B．线性表 C．队列 D．二叉排序树

6．已知主串s=″ADBADABBAAB″，模式串t=″ADAB″，则应用朴素的串匹配算法进行模式匹配过程中，无效位移的次数是（ B ） A．2 B．3 C．4 D．5

7．串s=″Data Structure″中长度为3的子串的数目是（ C ） A．9 B．11 C．12 D．14

8．假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是（ B ） A．R[3][3][3] B．R[3][3][4] C．R[4][3][5] D．R[4][3][4]

9．除第一层外，满二叉树中每一层结点个数是上一层结点个数的（ C ） A．1/2倍 B．1倍 C．2倍 D．3倍

10．对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（ D ） A．O（n） B．O(e) C．O(n+e) D．O(n2)

11．如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ B ） A．深度优先搜索算法 B．广度优先搜索算法 C．求最小生成树的prim算法 D．拓扑排序算法 12．快速排序在最坏情况下的时间复杂度是（ B ） A．O(n2log2n) B．O(n2) C．O(nlog2n) D．O(log2n)

13．能进行二分查找的线性表,必须以（ A ） A．顺序方式存储,且元素按关键字有序 B．链式方式存储,且元素按关键字有序 C．顺序方式存储,且元素按关键字分块有序 D．链式方式存储,且元素按关键字分块有序

14．为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为（ B ） A．05 B．37

C．41 D．62

15．ISAM文件的周期性整理是为了空出（ D ） A．磁道索引 B．柱面索引 C．柱面基本区 D．柱面溢出区

二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。

16．数据类型按其值能否分解,通常可分为____原子类型和结构类型_____两种类型。 17．队列的修改是按__先进先出_______的原则进行的。

18．两个串相等的充分必要条件是两个串的长度相等且_相应位置上的字符相等________。 19．数组采用顺序存储方式表示是因为通常不对数组进行___插入和删除______操作。 20．用广义表的取表头head和取表尾tail的运算，从广义表LS=(b,c,(f),((d)))中分解出原子c的操作为__head(tail(LS))_______。

21．结点数为20的二叉树可能达期的最大高度为____19_____。 22．带权连通图的生成树的权是该生成树上_各边的权值之和________。

23．所谓“就地排序”，是指排序算法辅助空间的复杂度为__O(1)_______的排序方法。 24．5阶B－树的根结点至少含有____4_____个关键字。

25．索引文件中的索引表指示记录的关键字与____物理记录_____之间一一对应的关系。 三、解答题（本大题共4小题，每小题5分，共20分）

26．假设以有序对表示从双亲结点到孩子结点的一条边，若已知树中边的集合为{,,,,,,,,,},请回答下列问题： （1）哪个结点是根结点？ （2）哪些结点是叶子结点？ （3）哪些结点是k的祖先？ （4）哪些结点是j的兄弟？ （5）树的深度是多少？

27．已知有向图G的深度优先生成森林和广度优先生成森林如下。请写出该图的深度优先遍历序列和广度优先遍历序列。

28．当将两个长度均为n的有序表A=（a1，a2，?，an）与B=（b1，b2，?，bn）(ai≠bj, 1≤i,j≤n)归并为一个有序表C=（c1, c2,?,c2n）时，所需进行的元素比较次数最少可达n,最多可达2n-1。

（1）假设有序表C=（2，4，5，6，7，9），试举出两组A与B的例子，使它们在归并过程中进行的元素比较次数分别达到最少和最多；

（2）写出一般情况下，使归并所需进行的元素比较次数分别达到最少和最多时，A与B中的元素应满足的条件。 （1） （2）

29．对下列关键字序列（33，25，48，59，36，72，46，07，65，20）构造表长为19的散列表。假设散列函数为h(key)=key,用开放地址法解决冲突，探查序列为d=h(key),d+12,d-12，d+2 2,d-2 2,d+32，d-32，?，等等。 （1）画出该散列表；

（2）计算该散列表的装填因子α；

（3）求出等概率情况下查找成功的平均查找长度ASL。 （1）（2）（3）

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

本文来源：https://www.bwwdw.com/article/jwo.html