全国2011年10月自考试卷02331数据结构

　　数据结构试题

　　课程代码：02331

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

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

　　1、在数据的逻辑结构中，树结构和图结构都是( )

　　A.非线性结构 B.线性结构

　　C.动态结构 D.静态结构

　　2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为( )

　　A.O(1) B.O(log n)

　　C.O(n) D.O(n2)

　　3.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为( )

　　A.p1->next=p2->next;p2->next=p1->next;

　　B. p2->next=p1->next;p1->next=p2->next;

　　C. p=p2->next; p1->next=p;p2->next=p1->next;

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

　　4.设栈的初始状态为空，入栈序列为1，2，3，4，5，6，若出栈序列为2，4，3，6，5，1，则操作过程中栈中元素个数最多时为( )

　　A.2个 B.3个

　　C.4个 D.6个

　　5.队列的特点是( )

　　A.允许在表的任何位置进行插入和删除

　　B.只允许在表的一端进行插入和删除

　　C.允许在表的两端进行插入和删除

　　D.只允许在表的一端进行插入，在另一端进行删除

　　6.一个链串的结点类型定义为

　　﹟define NodeSize 6

　　typedef struct node{

　　char data[NodeSize];

　　struct node*next;

　　}LinkStrNode;

　　如果每个字符占1个字节，指针占2个字节，该链串的存储密度为( )

　　A.1/3 B.1/2

　　C.2/3 D.3/4

　　7.广义表A=(a,B,(a,B,(a,B,……)))的长度为( )

　　A.1 B.2

　　C.3 D.无限值

　　8.已知10×12的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A[1][1]的存储地址为420，则A[5][5]的存储地址为( )

　　A.470 B.471

　　C.472 D.473

　　9.在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为( )

　　A.12 B.16

　　C.18 D.20

　　10.在带权图的最短路径问题中，路径长度是指( )

　　A.路径上的顶点数 B.路径上的边数

　　C.路径上的顶点数与边数之和 D.路径上各边的权值之和

　　11.具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为( )

　　A.e B.2e

　　C.n2-2e D.n2-1

　　12.要以O(n log n)时间复杂度进行稳定的排序，可用的排序方法是( )

　　A.归并排序 B.快速排序

　　C.堆排序 D.冒泡排序

　　13.若希望在1000个无序元素中尽快求得前10个挺大元素，应借用( )

　　A.堆排序 B.快速排序

　　C.冒泡排序 D.归并排序

　　14.对有序表进行二分查找成功时，元素比较的次数( )

　　A.仅与表中元素的值有关 B.仅与表的长度和被查元素的位置有关

　　C.仅与被查元素的值有关 D.仅与表中元素按升序或降序排列有关

　　15.散列文件是一种( )

　　A.顺序存取的文件 B.随机存取的文件

　　C.索引存取的文件 D.索引顺序存取的文件

　　二、填空题(本大题共10小题，每小题2分，共20分)

　　请在每小题的空格中填上正确答案。错填、不填均无分。

　　16.若一个算法中的语句频度之和为T(n)=3n3-200nlog2n+50n，则该算法的渐近时间复杂度为__________.

　　17.在单链表中，除了第1个元素结点外，任一结点的存储位置均由_____________指示。

　　18.栈的修改是按__________的原则进行。

　　19.字符串中任意个连续的字符组成的子序列称为该串的__________。

　　20.假设一个10阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，若矩阵中的第1个元素a11在B中的存储位置k=0，则元素a55在B中的存储位置k=__________。

　　21.在一棵具有n个结点的严格二叉树中，度为1的结点个数为__________。

　　22.对于稀疏图，采用__________表示法较为节省存储空间。

　　23.在排序过程中，如果_____________，则称其为外部排序。

　　24.设有一组记录的关键字为{19，14，23，1，68，12，10，78，25｝，用链地址法构造散列表，散列函数为h(key)=key%11,散列地址为1的链中有__________个记录。

　　25.多关键字文件的特点是除主文件和主索引外，还建有__________。

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

　　26.对于下列稀疏矩阵(注：矩阵元素的行列下标均从1开始)

　　(1)画出三元组表;

　　(2)画出三元组表的行表。

　　(1)

　　(2)

　　27.已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为ABCDEFGH。

　　(1)画出该森林;

　　(2)画出该森林所对应的二叉树。

　　(1)

　　(2)

　　28.对关键字序列(429，653，275，897，170，908，473，256，726)进行基数排序，写出每一趟的排序结果。

　　29.对下列关键字序列

　　(87，25，310，08，27，132，68，96，187，133，70，63，47，135)

　　构造散列表，假设散列函数为h(key)=key%13,用拉链法解决冲突。

　　(1)画出该散列表;

　　(2)求等概率情况下查找成功的平均查找长度ASL;

　　(3)写出删除值为70的关键字时所需进行的关键字比较次数。

　　(1)

　　(2)

　　(3)

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

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

　　(1)假设L=(3，7，7，11，20，20，20，51，51)，写出执行函数f30(&L)后的L;

　　(2)简述f30的功能。

　　void f30(SeqList*L)

　　{ ∥L为非空的有序表

　　int i=1,k=0;

　　while(ilength)

　　{

　　if(L->data[i]!=L->data[k])

　　L->data[++k]=L->data[i];

　　i++;

　　}

　　L->length=k+1;

　　}

　　(1)

　　(2)

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

　　(1)假设栈S=(3，8，6，2，5)，其中5为栈顶元素，写出执行函数f31(&S)后的S;

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

　　void f31(Stack *S){

　　Queue Q;InitQueue(&Q);

　　while(!StackEmpty(S))

　　EnQueue(&Q,Pop(&S));

　　while(!QueueEmpty(Q))

　　Push(&S,DeQueue(&Q));

　　}

　　(1)

　　(2)

　　32.假设具有n个结点的完全二叉树顺序存储在向量BT[1.. n]中，阅读下列算法，并回答问题：

　　(1)若向量BT为：

　　ABCDEFG

　　1 2 3 4 5 6 7

　　画出执行函数f32(BT,7,1)的返回结果;

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

　　BinTree f32(DataType BT[],int n,int i)

　　{

　　BinTree p;

　　if (i>n) return NULL;

　　p=(BinTNode*)malloc(sizeof(BinTNode));

　　p->data=BT[i];

　　p->lchild=f32(BT,n,i*2);

　　p->rchild=f32(BT,n,i*2+1);

　　return p;

　　}

　　(1)

　　(2)

　　33.已知有向图的邻接表和邻接矩阵定义如下：

　　﹟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; ∥邻接表描述的图

　　typedef struct{

　　char vertex[MaxNum]; ∥顶点表

　　int adjmatrix [MaxNum][MaxNum]; ∥邻接矩阵

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

　　} AMGraph; ∥邻接矩阵描述的图

　　下列算法是将邻接表描述的图G1改为邻接矩阵描述的图G2，在空白处填上适当内容使算法完整：

　　void f33(ALGraph G1,AMGraph *G2)

　　{ int i, j;

　　EdgeNode *p;

　　G2->n=G1.n;

　　G2->e= (1) ;

　　for (i=0; i

　　{ G2->vertex[i]= (2) ;

　　p=G1.adjlist[i].firstedge;

　　for (j=0; jadjmatrix[i][j]=0;

　　while (p)

　　{ G2->adjmatrix[i][p->adjvex]=1;

　　(3) ;

　　}

　　}

　　}

　　(1)

　　(2)

　　(3)

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

　　34.设顺序表L是一个递增有序表。编写算法，要求利用二分查找法确定插入位置，将元素x插入到L中，使L保持有序。

　　本自考试题下载：全国2011年10月自考试卷02331数据结构

山东自考助学报名预约

请选择您的报考层次 大专 本科 专本套读

提交报名信息 重置信息

我已阅读并同意《用户隐私条款》

个人信息授权与保护声明

关闭

鉴于网络的特性，本网站将无可避免地与您产生直接或间接的互动关系，故特此说明本网站对用户个人信息所采取的收集、使用和保护政策，请您务必仔细阅读：

信息收集范围

我们根据合法、正当、必要的原则，仅收集为您提供服务所必要的信息。包括：

1、您在使用我们服务时主动提供的信息

(2)您通过电话咨询方式提供的姓名、电话、住址、微信/QQ、备注等信息。

(3)您在使用网上咨询服务所提供的姓名、电话、住址、微信/QQ、备注等信息。

(4)您参与我们线上活动时填写的调查问卷中可能包含您的姓名、电话、地址等信息。

我们的部分服务可能需要您提供特定的个人敏感信息来实现特定功能。

若您选择不提供该类信息，则可能无法正常使用服务中的特定功能，但不影响您使用服务中的其他功能。

若您主动提供您的个人敏感信息，即表示您同意我们按本政策所述目的和方式来处理您的个人敏感信息。

本次报名数据服务由本网站提供，本网站不承担由于内容的不一致性所引起的一切争议和法律责任，报名结果以最终辅导报名系统为准。

信息使用用途

我们严格遵守法律法规的规定及与用户的约定，将收集的信息用于以下用途。若我们超出以下用途使用您的信息，我们将再次向您进行说明，并征得您的同意。

1、通过微信、电话形式建立沟通，向您提供学历咨询服务。

2、满足您的个性化需求。例如，学历途径规划、学历评估等。

3、项目开发和服务优化。例如，通过您的咨询问题及服务过程中您的建议等，优化我们的服务。

4、向您推荐您可能感兴趣的学校、资讯等。

5、学校推荐。例如，我们会根据您的具体要求以您所具备的条件向您推荐合适的院校。

为了让您有更好的体验、改善我们的服务或经您同意的其他用途，在符合相关法律法规的前提下，我们可能将通过某些服务所收集的信息用于我们的其他服务。例如，将您在使用我们某项服务时的信息，用于另一项服务中向您展示个性化的内容或广告、用于用户研究分析与统计等服务。

信息保护

我们仅在本《隐私政策》所述目的所必需的期间和法律法规要求的时限内保留您的个人信息。

本网站将对您所提供的资料进行严格的管理及保护，本网站将使用相应的技术，防止您的个人资料丢失、被盗用或遭篡改。

当政府机关依照法定程序要求本网站披露个人资料时，本网站将根据执法单位之要求或为公共安全之目的提供个人资料。在此情况下之任何披露，本网站均得免责。

由于您将用户密码告知他人或与他人共享注册帐户，由此导致的任何个人资料泄露。任何由于计算机问题、黑客政击、计算机病毒侵入或发作、因政府管制而造成的暂时性关闭等影响网络正常经营之不可抗力而造成的个人资料泄露、丢失、被盗用或被篡改情况时本网站亦毋需承担任何责任。

未成年人保护

本网站将建立和维持一合理的程序，以保护未成年人个人资料的保密性及安全性。本网站郑重声明：任何16岁以下的未成年人参加网上活动应事先得到家长或其法定监护人的可经查证的同意。若您是未成年人的监护人，当您对您所监护的未成年人的个人信息有相关疑问时，请通过与我们联系。

适用范围

我们的所有服务均适用本政策。但某些服务有其特定的隐私指引/声明，该特定隐私指引/声明更具体地说明我们在该服务中如何处理您的信息。如本政策与特定服务的隐私指引/声明有不一致之处，请以该特定隐私指引/声明为准。

您必须完全同意以上协议才能使用本网站的在线报名服务。