2018年4月高等教育自学考试《数据结构》试题
课程代码：02331
一、单项选择题
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．二维数组M，行下标取值范围为0—8，列下标取值范围为1～10，若按行优先存储时，元素M[8Ⅱ51的存储地址为ar，则按列优先存储时，地址ar存储的数组元素应是
A．M[8][5] B．M[5][8] C．M[3][10] D．M[0][9]
7．根据二叉树的定义，3个结点构成的二叉树的树型有
A．2种 B．3种 C．4种 D．5种
8．一棵有序树可转换为一棵二叉树，树的后序遍历对应二叉树的
A．前序遍历 B．中序遍历 C．后序遍历 D．以上都不对
9．若图G的邻接表中有奇数个表结点，则G是
A．含奇数个顶点的图 B．无向图
C．含偶数个顶点的图 D．有向图
10．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑排序序列的结论是
A．存在，且唯一 B．存在，且不唯一
C．存在，可能不唯一 D．无法确定是否存在
11．如果无向图G的最小生成树T中含有边(a，b)和(a，c)，则下列选项中，一定不在T中的边是
A． (b，c) B． (b，d) C． (c，d) D． (c，e)
12．下列排序算法中，在每一趟都能选出一个元素放到其最终位置上的是
A．插入排序 B．希尔排序 C．归并排序 D．堆排序
13．若数据元素序列11，13，15，7，8，9，23，2，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法是
A．冒泡排序 B．插入排序 C．选择排序 D．归并排序
14．线性表采用顺序存储或链式存储，对其进行查找的方法应是
A．顺序查找 B．二分查找 C．散列查找 D．索引查找
15．设有序表为{1，3，9，12，32，41，45，62，75，77，82}，采用二分查找法查找关键字75，查找过程中关键字之间的比较次数是
A．1 B．2 C．3 D．4
二、填空题
16．在数据结构中，从逻辑上可以把数据结构分为线性结构和 。
17．为便于实现单链表的插入及删除运算，需要在单链表中增加一个结点，该结点称为 。
18．在二维数组A(10Ⅱ8]中，每个数组元素占用4个存储单元，则数组A需要的存储单元个数是 。
19．对长度为1的广义表A，若有Head(A)=Tail(A)，则A= 。
20．设高为h的二叉树T中只有度为0和2的结点，则T包含的结点数最多为 。
21．一个连通图的 是包含图中所有顶点的极小连通子图。
22．无向图G中含7个顶点，顶点间的边是随机设置的，为保证图G在任何情况下都是连通的，则需要的边数最少是 。
23．求单源最短路径的迪杰斯特拉(Dijkstra)算法是按照路径 不减的次序求出各条路径的。
24．一组记录的关键字为(45，53，18，49，36，76，13，97，36，32)，利用快速排序方法对其进行排序，选择45为基准，一次划分后的结果为 。
25．对箱排序的改进和推广的排序算法是 。
三、解答题
26．两个栈共享数组空间data[m](定义如下)，它们的栈底分别设在数组的两端(初始
化后 top1 = - 1, top2 = m)。
typedef struct {
DataType data[m];
int top1, top2;
}SeqStack;
回答下列问题。
(1)编写判断栈满的函数ht stackfull(SeqStack *s)；
(2)编写进栈函数voidpush(SeqStack *s， int si， DataType x)，
其中，si取值为0、1，分别表示栈底为0或m-1的栈。
27．已知二叉树T中含有元素A，B，C，D，E，F，G，H，了的前序遍历序列、中序遍历序列和后序遍历序列如下，其中符号—表示未知元素。试写出①到⑩所代表的正确元素值。
28．设图G如题28图所示。
回答下列问题。
(1)图G是否是有向无环图?
(2)给出图G所有的拓扑排序序列。
29．设关键字序列为：53，15，72，52，48，67，63，23。已知散列表地址空间为0～11，散列函数为H(k)=kmod11，采用线性探查再散列法解决冲突。
(1)将所给关键字数据依次填入该散列表中：
(2)计算等概率下查找成功的平均查找长度。
四、算法阅读题
30．已知队列的基本操作定义如下，请在空白处填写适当的语句，完成指定的功能。
#define QueueSize 100typedef struct { // 队列定义char data[QueueSize];int front, rear;} CirQueue;CirQueue Q;void InitQueue( CirQueue *Q ) //队列初始化{ Q->front = Q->rear = 0;}int QueueEmpty( CirQueue *Q ) //判队列是否空{ return ( 1 ) ;}int QueueFull( CirQueue *Q ) //判队列是否满{ return (Q->rear+l) % QueueSize ==Q->fi.ont;char EnQueue( CirQueue *Q, char c ) // 入队操作{ if (QueueFull( Q ) )return '\0'; // 操作失败else{ Q->data[Q->rear] = c;Q->rear= (2)return c; //操作成功}char DeQueue( CirQueue *Q ) //出队列操作{ char x;if( QueueEmpty( Q ) )return 'Eh'; //操作失败else{ x = Q->data[ Q->front ];Q->fi-om = (3)return x; // 操作成功}}
31．程序61是将输入的m行n列的二维数组a变换为三元组表形式存储在数组b中。请在空白处填上适当内容将算法补充完整。
#define MAXSIZE 100typedef iht DataType;typedef struct {int i,j; // 非零元素行列下标DataType v, // 非零元素值}TriTupleNode;typedef struct {TriTupleNode data[MAXSIZE]; // 存储三元组数组int m, n,t; //m：矩阵的行,n: 矩阵的列, t：非零元素数量} TSMatrix;void t31 ( TSMatrix *b, int *a, int m, int n)// 将m行n列的矩阵a变换为三元组表形式存储在b{ ihti, j, k=-O;for (i=O; i<m; i++)for (j=0; j<n; j++){ if ( *a !=0 ){ b->data[k].i = i;b->data[kl.j =j;b->data[k].v = ( 1 ) ;(2) ;}a++;}b->m = m;b->n = n;b->t = (3)}
32．已知二叉树T如题32图所示。阅读程序62，写出执行B2(T)的输出结果。
typedef char DataType;typedef struet node{DataType data; //data是数据域struet node * lchild, * rchild; // 分别指向左右孩子}BinTNode;typedefBinTNode* BinTree;void f32 ( BinTree bt ){if(bt!=NULL){f32 (bt->rchild);printf("%c", bt->data);f32 (bt->lchild);}}执行结果：33．阅读程序，写出执行结果。void 133( int a[], iht n ){ mti;for ( i=(n-1)/2; i>=0; i-- )Sift(a, i, n-l);}void Sift( iht a[], iht i, int h){ int j, teml=a[i];j= 2'i+1;while (j <= h ){ if (j<h && a[j] <a[j+l] )j ++;if ( temp >= a[j] )break;alii = a[j];i =j;j = 2'i+1;}a[i] = temp;}ihtmain(){ int i, a[10] = { 10, 20, 5, 23,25, 62, 21, 1, 32, 9 };t33( a, 10 );for ( i=0; i<10; i++ )printfC%d='', alii);printff"\n");return 0;}执行结果：
五、算法设计题
34．已知带有头结点的单链表定义如下：
typedef struct node
{ char ch;
struct node *next;
} ListNode;
typedef ListNode *LinkList;
请编写函数intf34(LinkList h, char string[])，根据输入的字符串，建立不含重复字符的链表。
2018年10月高等教育自学考试《数据结构》试题
课程代码：02331
一、单项选择题
1．下列数据结构中，逻辑结构不同的是
A．线性表 B．栈 C．队列 D．二叉树
2．将16个数据元素的线性表按顺序存储方式存储在数组中，若第一个元素的存储地址是1000，第6个元素的存储地址是1040，则最后一个元素的存储地址是
A．1112 B．1120 C．1124 D．1128
3．设栈的初始状态为空，元素1,2,3,4,5依次入栈，不能得到的出栈序列是
A．1，2，3，4，5 B．4，5，3，2，1
C．1，2，5，4，3 D．1，2，5，3，4
4．设指针变量p指向非空单链表中的结点，next是结点的指针域，则判断p所指结点为尾结点前一个结点的逻辑表达式中，正确的是
A．p->next!=NULL&&p->next->next->next==NNULL
B．p->next!=NULL&&p->next->next==NULL
C．p->next->next==NULL
D．p->next==NULL
5．已知广义表LS=(((a,b,c),d)，(e,(f,8),(h,i)))，LS的深度是
A．2 B．3 C．4 D．5
6．己知一棵完全二叉树T的第5层上共有5个叶结点，则T中叶结点个数最少是
A．5 B．8 C．10 D．27
7．已知二叉树T的前序遍历序列为a，b，c，e，d，中序遍历序列为c，e，b，d，a，则T的后序遍历序列为
A．c，e，d,b，a B．d,e，c，b，a C．e，c，d，b，a D．e，c，b，a，d
8．有向图G有n个顶点和e条边，G保存在邻接矩阵M中，M中0与1的个数差是
A．n(n+1)／2-e B．n(n+1)／2-2e C．n×n-e D．n×n-2e
9．有向图G中所有顶点的度数之和是24，则G中弧的数量是
A．10 B．12 C．14 D．16
10．设有向图G含有／1个顶点、e条边，使用邻接表存储，对G进行深度优先搜索遍历算法的时间复杂度是
A．O(n) B． O(e) C．O(n+e) D．O(n×e)
11．对数据序列(26，14，17，12，7，4，3)采用二路归并排序进行升序排序，两趟排序后，得到的排序结果为
A．14，26，17，12，4，7，3 B．12，14，17，26，3，4，7
C．14，26，12，17，3，4，7 D．14，26，12，17，3，7，4
12．下列选项中，不稳定的排序方法是
A．希尔排序 B．归并排序 C．直接插入排序 D．冒泡排序
13．一组记录的关键字为(35，48，47，23，44，88)，利用堆排序算法进行降序排序，建立的初始堆为
A．23，35，48，47，44，88 B．23，35，47，48，44，88
C．35，23，47，48，44，88 D．35，23，47，44，48，88
14．一棵二叉排序树中，关键字n所在结点是关键字m所在结点的孩子，则
A．n一定大于m B．n一定小于m
C．n一定等于m D．n与m的大小关系不确定
15．设散列表长m=16，散列函数H(key)=key％15。表中已保存4个关键字：addr(18)=3，addr(35)=5，addr(51)=6，addr(22)=7，其余地址均为开放地址。存储关键字36时存在冲突，采用线性探测法来处理。则查找关键字36时的探查次数是
A．1 B．2 C．3 D．4
二、填空题
16．数据项是具有独立含义的 标识单位。
17．指针p和q分别指向单链表l中的两个相邻结点，即q->next=p。若要在q所指结点后插入指针r所指结点，则执行的语句是r->next=p； 。
18．递归算法设计中的最小子问题称为递归的 。
19．广义表((a,b),(c,d),e,(f,(g,h)))的表尾是 。
20．已知二叉树的前序遍历序列和后序遍历序列，则对应的二叉树 确定。
21．如果有向无环图G中仅有一个顶点的入度为0，若要求G的拓扑序列不唯一，则G中必须存在一个出度至少为 的顶点。
22．将森林T转换为一棵二叉树T1，在T中结点A是结点B的右邻的兄弟(下一个兄弟)，则在T1中，A是B的 。结点。
23．对含n个元素的数据序列采用快速排序算法进行排序，平均时间复杂度是 。
24．散列存储中，常用的解决冲突的方法有开放地址法和 两大类。
25．假设顺序存储的有序表R含有8个关键字，进行二分查找时，平均查找长度为 。
三、简答题
26．设电文字符集是{e1,e2,e3,e4,e5}，各字符出现的次数分别为{36，13，26，18，23)。现要为该字符集设计哈夫曼编码。请回答下列问题。
(1)给出构造的哈夫曼树。
(2)给出各字符的哈夫曼编码。
(3)计算电文编码总长。
27．已知图G采用邻接矩阵存储，邻接矩阵如题27图所示
(1)根据邻接矩阵画出图G。
(2)根据图G写出从顶点A开始图G的1个深度优先搜索遍历序列。
(3)根据图G写出从顶点A开始图G的1个广度优先搜索遍历序列。
28．有数据序列(12，17，05，10，20，24，45，11，10，12)，使用希尔排序方法将其排成升序序列。请回答下列问题。
(1)分别写出增量为3和1的希尔排序结果。
(2)计算第一趟希尔排序中数据元素之间的总交换次数(两个元素之间的交换记1次)。
29．设有二叉排序树T如题29图所示。现需在T中删除结点e，请回答下列问题。
(1)画出删除后的二叉排序树(仅需画出一棵)。
(2)在你实现的删除过程中，指针域更新的次数是多少?
四、算法阅读题
30．顺序表类型定义如下：
//define ListSize 100typedef struct {intdata[ListSize];int length;} SeqList;阅读下列程序，并回答问题。int partmin(SeqList *SL1, SeqList *SL2){ iht minlength,minvalue, k=0;minlength =SL2->length;minvalue =SL2->data[0];while( k <minlength ) {if(SLl->data[k] < SL2->data[k] && SLl->data[k]<minvalue )minvalue = SL1->data[k];else if(SL2->data[k]<minvalue )minvalue = SL2->data[k];k++;returnminvalue;}int f30( SeqList *SL1, SeqList *SL2 ){if( SL1->length > SL2->length) return partmin(SL1, SL2 );else return partmin( SL2, SL1 );}
(1)若SL1->data中的数据为(15，14，25，8，-28，37，126，56，34)，SL2->data中的数据为(12，7，-33，15，39，24，42，13)，则调用函数t30(&SL1，&SL2)后的返回值是什么?
(2)该函数的功能是什么?
31．二叉树的存储结构类型定义如下：
typedef char DataType;typedef struet node{ DataTypedata; //data 是数据域struet node *lehild, * rehild; // 分别指向左右孩子}BinTNode;typedefBinTNode * BinTree;阅读下列程序，并回答问题。void f31 ( BinTree T )( if( T!=NULL) {t31(T->rchild );printf('%0 ", T->data );f31 (T->lchild );}return;}
(1)设二叉树T如题31图所示，给出执行f31(T)的输出结果。
(2)给出该算法的时间复杂度。
32．待排序记录的数据类型定义如下：
#define MAXSIZE 100typedefint KeyType;typedef street {KeyType key;} RecType;typedef RecType SeqList [MAXSIZE];
下列函数实现顺序表的直接插入排序，请填上适当内容使算法完整。
void f32( SeqList R, int n)int i,j;RecType temp;for (i=l;i<= (1) ;i++) {temp =R[i];j=i;while (j> 0 && temp.key < R[j-1 ].key ) {R[j] =R[j-1];(2) ;}(3) ;}}
33．二叉树的存储结构类型定义如下：
typedef int DataType;typedef struct node{DataTypekey; //data是数据域street node *lchild, * rchild; //分别指向左右孩子}BinTNode;typedefBinTNode * BinTree;阅读下列程序，并回答问题。void f33( BinTree root, int left, int right ){if(root=NULL)return;f33(root->lehild, left, fight );if(root->key >= left && root->key<right ) printf( "%d", root->key );f33(root->rehild, left, right );}
(1)设二叉树T如题33图所示，bt是指向根结点的指针。给出执行f33和(bt,14,30)的输出结果。
五、算法设计题
34．已知n个单链表的表头指针保存在数组A中，单链表中的结点类型及数组类型定义如下，存储形式如题34图所示。
#define MAXSIZE 100typedef int DataType;typedef struct node{ DataTypedata; //data是数据域stmct node*next; //指向下一结点的指针}Node;typedefNode * SeqList [MAXSIZE];
试设计算法，在多个链表中查找值为key的数据元素，查找成功返回1，查找失败返回0。函数原型为intf34(SeqList A, int n，int key)。
2019年10月高等教育自学考试《数据结构》试题
课程代码：02331
一、单项选择题
1．下列选项中，不宜采用链式存储的是
A．无向图 B．单链表 C．最优二叉树 D．数组
2．将10个数据元素保存在顺序栈S中，若栈顶元素的存储地址是100，栈中每个元
素占4个存储单元，进栈按S.top=S.top+l修改栈顶，则栈底元素的存储地址是
A．60 B．64 C．136 D．140
3．设指针变量head指向循环链表的头结点，next是结点的指针域，则判断此链表为
空的条件是
A．head->next==NULL B．head->next==head
C．head->next!=NULL D．head->next!=head->next
4．己知广义表LS=(((a,b,c)),((d,(e)),(f,(g))),(h,9),i》,LS的深度是
A．4 B．3 C．2 D．1
5．己知一棵完全二叉树T共有7个分支结点，则T中叶子结点个数最少是
A．7 B．8 C．9 D，10
6．在一棵非空二叉树的后序遍历序列中，所有列在根结点前面的是
A．左子树中的部分结点 B．右子树中的全部结点
C．左右子树中的全部结点 D．左右子树中的部分结点
7．用邻接表保存有n个顶点和e条边的无向图，邻接表中指针个数是
A．e B．n-e C．n+e D．n+2e
8．有向图G中某个顶点的出度和入度均为2，则G中的顶点个数最少是
A．2 B．3 C．4 D．5
9．在带权图的最短路径问题中，路径长度是指
A．路径上边的数目 B．路径上结点的数目
C．路径上边的权值之和 D．到达终点的最短路径数目 ．
10．对数据序列(15，10，8，12，15，8，10)按升序进行希尔排序，增量序列为5，3，两趟排序后，得到的排序结果为
A．8，8，10，10，15，15，12 B．8，8，10，10，12，15，15
C．8，10，8，10，15，15，12 D．8，10，8，10，12，15，15
11．下列排序方法中，不稳定的排序方法是
A．直接选择排序 B．归并排序 C．直接插入排序 D．基数排序
12．一组记录的关键字为(35，58，24，13，44，19，10)，利用堆排序算法进行降序排序，要求空间复杂度为O(”，建立的初始堆为
A．10，13，19，58，44，35，24 B．10，13，35，58，44，19，24
C．58，44，24，13，35，19，10 D．58，35，24，13，44，19，10
13．一棵二叉排序树中，关键字n所在结点的层数大于关键字m所在结点的层数，则
A．n一定大于m B．n一定小于m
C．n一定等于m D．n与m的大小关系不确定
14．设散列表长m=10，散列函数H(key)=key％9。表中已保存3个关键字：H(13)=4，
H(32)=5，H(15)=6，其余地址均为空。保存关键字23时存在冲突，采用线性探
查法来处理。则查找关键字23时的探查次数是
A。1 B．2 C．3 D．4
{ int k, m;for ( k = O; k < n; k++ ){ if ( pdata[k]%2 -- 0 )SL->data[ SL->length ] = pdata[ k ];else{ for ( m = SL->length; m > O; m-- )SL->data[ m ] = SL->data[ m-1 ];SL->data[O] = pdata[k];}SL->length ++;}}void out( SeqList *SList ){ intk= O;while ( k < SList->length ) // 顺序输出SList 中的各个元素printf("%d, ", SList->data[ k++ ]);}int main(){ int array[] = { 10, 2, 9, 5, 30, 3 };SeqList Mist;Mist. length = O;f30( &slist, array, sizeof(array)/sizeof(int) );out( &slist ); // 输出 slistreturn O;}
(1)执行程序后程序的输出是什么?
(2)函数D00的功能是什么?
31．二叉树的存储结构类型定义如下。
typedef int DataType;typedef struct node{ DataType data; //data :是数据域stmct node * lchild, * rchild; // 分别指向左右孩子} BinTNode;typedef Bin TNode * Bin Tree;阅读下列函数并回答问题。void f31 ( BinTree Bt ){ if ( Bt != NULL ). {, if( Bt->lchild ==- NULL && Bt->rchild == NULL )Bt->data = Bt->data*2;else{ f31( Bt->lchild );f31( Bt->rchild );}}}
(1)设二叉树Bt如题31图所示，给出执行f31(Bt)的输出结果。
(2)该算法的功能是什么?
32．待查找记录的数据类型定义如下。
//define MAXSIZE 100typedef int KeyType;typedef struct {KeyType key;} RecType;typedefRecType SeqList[ MAXSIZE ];
下列算法实现对按升序排列的数据进行二分查找。请在空白处填上适当内容使算法完整。
iht BinSearch( SeqList R, KeyType k, int n ){ int low = 0, high = n-l, mid;while ( low <= high ){ mid = ( low+high )/2;if ( ( 1 ) ) return mid;else if ( R[mid].key > k ) high -- (2) .;else low = (3) ;}return - 1;}
33．二叉树的存储结构类型定义如下。
typedef int DataType;typedef struct node{ DataType data; //data 是数据域，其值大于0structnode *lchild, *rchild; // 分别指向左右孩子} BinTNode;typedefBinTNode * BinTree;
下列程序的功能是：将一棵二叉树的顺序存储结构转换为对应的链式存储结构。
例如，对如题33图所示的二叉树，二叉树的顺序存储序列如下。
int data[]={30，20，0，0，90，0，0，0，0，100}；
程序如下：Bin Tree create( int *data, int n ){ BinTNode *Q[100], *Bt = NULL, *p;int front = 0, rear = 0, k;for(k=0; k(n;k++){ p = NULL;if ( data[k] != 0 ){ p = (BinTree)malloc(sizeof(BinTNode) );p->data = data[k];p->Ichild = p->rchild = NULL;}Q[ rear++] =p;if ( rear＝1 ) Bt = p;else{ if ( p != NULL && ( 1 )if( (2) ==0 )Q[front]->lchild = p;elseQ[fi'ont]->rchild = p;if ( rear%2 != 0 )(3)}}return Bt;}
请在程序的空白处填入适当的语句，使程序完整正确。
五、算法设计题
34．单链表类型定义如下。
typedef struct node{ int data;stmct node *next;} ListNode;typedef ListNode *LinkList;
请编写一个函数，在带头结点的单链表L中删除数值在指定范围内(x≤data≤y)
的结点。函数的原型如下。
Void f34(LinkList L，inty)；
例如，对于如下的链表head，
联系客服
