全国2004年1月高等教育自学考试 数据结构试题.doc

《全国2004年1月高等教育自学考试 数据结构试题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、全国2004年1月高等教育自学考试数据结构试题课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．在数据结构中，数据的逻辑结构可以分成（　　　）A．内部结构和外部结构B．线性结构和非线性结构C．紧凑结构和非紧揍结构D．动态结构和静态结构2．在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（　　　）A．数据元素的相邻地址表示B．数据元素在表中的序号表示C．指向后继元素的指针表示D．数据元素的值表示3．设p指向单链表中的一个结点，s指

2、向待插入的结点，则下述程序段的功能是（　　　）　　　　　s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;A．结点*p与结点*s的数据域互换B．在p所指结点的元素之前插入元素C．在p所指结点的元素之后插入元素D．在结点*p之前插入结点*s4．栈和队列都是（　　　）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构5．若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的

3、最佳方案是：s1和s2的栈顶指针的初值分别为（　　　）A．1和n+1B．1和n/2C．－1和nD．－1和n+16．执行下列程序段后，串X的值为（　　　）S=〞abcdefgh〞;T=〞xyzw〞;substr(X,S,2,strlen(T));substr(Y,S,stelen(T),2);strcat(X,Y);A．〞cdefgh〞B．〞cdxyzw〞C．〞cdefxy〞D．〞cdefef〞7．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（　　　）A．数组的元素处在行和列两个关系中B．数组的元素必须从左到右顺序排列C．数组的元素之间存在次序关系D．数组是多

4、维结构，内存是一维结构8．从广义表LS＝（(p,q),r,s）中分解出原子q的运算是（　　　）A．tail(head(LS))B．head(tail(head(LS)))C．head(tail(LS))D．tail(tail(head(LS)))9．在具有n个叶子结点的严格二叉树中，结点总数为（　　　）A．2n+1B．2nC．2n-1D．2n-210．若是有向图的一条边，则称（　　　）A．vi邻接于vjB．vj邻接于viC．vi和vj相互邻接D．vi与vj不相邻接11．在一个带权连通图G中，权值最小的边一定包含在G的（　　　）A．最小生成树中B．深度优先

5、生成树中C．广度优先生成树中D．深度优先生成森林中12．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（　　　）A．左子树的叶子结点B．左子树的分支结点C．右子树的叶子结点D．右子树的分支结点13．希尔排序的增量序列必须是（　　　）A．递增的B．随机的C．递减的D．非递减的14．如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（　　　）A．插入排序B．归并排序C．冒泡排序D．堆排序15．设置溢出区的文件是（　　　）A．索引非顺序文

6、件B．ISAM文件C．VSAM文件D．顺序文件二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。16．下列程序段的时间复杂度为________________。　　product=1;　　for(i=n;i>0;i--)　　　for(j=i+1;jnext=p->next->next的作用是________________。18．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序

7、列为________________，不可能得到的出栈序列为________________。19．若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为________________。20．右图表示的广义表为________________。21．若一棵满三叉树中含有121个结点，则该树的深度为________________。22．若以邻接矩阵表示有向图，则邻接矩阵上　第i行中非零元素的个数即为顶点vi的________________。23．若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个