你可以上衡水自考网或者在里面去找一下答案.应该能找到一两年答案,但想要这几年全部的答案真的比较困难希望你好运
《数据结构》试题一、选择题（每小题2分，共30分）1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A、单链表 B、双链表 C、单向循环 D、顺序表2． 串是任意有限个（ ）A、符号构成的序列 B、符号构成的集合C、字符构成的序列 D、字符构成的集合3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足：aij≠0(i≥j, l≤i, j≤ 10)aij=0 (i。( )i6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( )7．“顺序查找法”是指在顺序表上进行查找的方法。（ ）8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）9．键值序列{A，C，D，E，F，E，F}是一个堆。10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（） 三、填空题（每小题2分，共20分）1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；2．有一个长度为20的有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找长度为3。3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为＿＿＿＿＿。若A的初始状态为递减排列，则记录的交换次数为＿＿＿＿＿＿＿。4．在无头结点的双链表中，指针P所指结点是第一个结点的条件是＿＿＿＿＿＿。5．G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是＿＿＿＿＿图。6．如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。7．深度为8（根的层次号为1）的满二叉树有＿＿＿＿＿＿个叶子结点。 8．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为＿＿＿＿＿＿＿。9．设某闭散列表HT未满，散列函数H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。void printword(keytype HT[m]) { for(i=1;i<=26;i++) { j=i; while(____________________) { if (____________________) printf(“datatype”,HT[j]); j=(j+1)% m; } } }10．设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p)；p->data=x; p->next=NULL；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； 四、简答题：（每小题4分，共20分）1. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？3. 设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？4. 在KMP算法中，已知模式串为ADABCADADA ，请写出模式串的next[j]函数值。5. 中序遍历的递归算法平均空间复杂度为多少？ 五、 算法设计题（每小题10分，共20分）1. 试编写一个算法，判断一给定的整型数组a[n]是不是一个堆。2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。参考答案一、选择题1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C 13、B14、C15、D二、判断题 1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. × 三、填空题1．U=L - > next2．4。3．n-1、n(n-1)/2。4．p - > prior = NULL。5．连通6．回路或环7．28-1 = 27 = 1288．249．HT[j]!=NULL或HT[j]不为空、H(HT[j])=I10．rear - > next = p、rear = p四、简答题：1. 答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。2.答：是：ABDEGCFH3. 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)； 即O（1000log21000）=O(10000) 锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）4. 答： 01121123435. 答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为O(log2n) 五、 算法设计题1.解：提示：堆的定义是：kia[2*i]|| a[i]>a[2*i+1])return(-1);return(minleap)};else { for( i=1; i<=n/2; i++) if (a[i]lchild) EnQueue(Q,{r.node->lchild, r.layer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1}); } //按层序入队时要随时标注结点所在层号 h=r.layer; //最后一个队列元素所在层就是树的高度 for(maxn=count[0], i=1; h; i++) if(count[i]>maxn) maxn=count[i]; //求出哪一层结点数最多 return (h*maxn)} // Width
深度的递归算法int depth(BiTreeNode * T){ if(T==NULL) return 0; // 如果结点为空，高度为0 else { int h1= depth(T->lchild); // 获得左子树的高度 int h2= depth(T->rchild); // 获得右子树的高度 return max(h1,h2)+1; }}
全国2003年上半年自考数据结构答案及标准评分 2006年10月自学考试"数据结构"试题参考答案 很多数据结构试题 自考用的数据结构课后答案 DOC文件，很大，现只复制最前面的一小部分，如需要，提供邮箱，我发给你(还有“数据结构试题及答案”) 第一章 绪论 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 ● 数据：指能够被计算机识别、存储和加工处理的信息载体。 ● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。 ● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。 ● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 ● 逻辑结构：指数据元素之间的逻辑关系。 ● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构. ● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。 ● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 答： 例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。 这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。 在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。 1.3 常用的存储表示方法有哪几种? 答： 常用的存储表示方法有四种: ● 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。 ● 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。 ● 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。 ● 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 1.4 设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) 分析： 数学符号"O"的严格的数学定义： 若T（n）和f（n）是定义在正整数集合上的两个函数，则T（n）=O（f（n））表示存在正的常数C和n0，使得当n≥n0时都满足0≤T（n）≤C•f（n）。 通俗地说，就是当n→∞时，f(n)的函数值增长速度与T（n)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。 即： O(f(n))=n3 O(g(n))=n3 O(h(n))=n1.5 所以答案为： 答： ●（1）成立。 ●（2）成立。 ●（3）成立。 ●（4）不成立。
自考数据库系统原理历年真题如下：
（1）试为该图书借阅系统设计一个ER模型，要求标注联系类型，可省略实体属性。
（2）根据转换规则，将ER模型转换成关系模型，要求标注每个关系模式的主键和外键（如
果存在）。
关于数据库的介绍如下：
数据库是存放数据的仓库。它的存储空间很大，可以存放百万条、千万条、上亿条数据。但是数据库并不是随意地将数据进行存放，是有一定的规则的，否则查询的效率会很低。当今世界是一个充满着数据的互联网世界，充斥着大量的数据。
即这个互联网世界就是数据世界。数据的来源有很多，比如出行记录、消费记录、浏览的网页、发送的消息等等。除了文本类型的数据，图像、音乐、声音都是数据。
数据库是“按照数据结构来组织、存储和管理数据的仓库”。是一个长期存储在计算机内的、有组织的、可共享的、统一管理的大量数据的集合。
在数据库的发展历史上，数据库先后经历了层次数据库、网状数据库和关系数据库等各个阶段的发展，数据库技术在各个方面的快速的发展。
可以转发一份给我吗，谢谢
全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; inext==head B. p->next->next==headC. p->next==NULL D. p==head4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ ）A. SXSSXXXX B. SXXSXSSXC. SXSXXSSX D. SSSXXSXX5.两个字符串相等的条件是（ ）A. 串的长度相等 B. 含有相同的字符集C. 都是非空串 D. 串的长度相等且对应的字符相同6.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（ ）A. head (tail (head (L))) B. head (head(head(L)))C. tail (head (tail (L))) D. head (head (tail (L)))7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）A. 0 B. 1C. 48 D. 498.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ）A. Dout B. Dout-1C. Dout+1 D. n9.如图所示的有向无环图可以得到的拓扑序列的个数是（ ）A. 3 B. 4C. 5 D. 610.如图所示的带权无向图的最小生成树的权为（ ）A. 51 B. 52C. 54 D. 5611.对长度为n的关键字序列进行堆排序的空间复杂度为（ ）A. O（log2n） B. O（1）C. O（n） D. O（n*log2n）12.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为（35，51，24，13，68，56，42，77，93）（35，24，13，51，56，42，68，77，93）所采用的排序方法是（ ）A. 插入排序 B. 冒泡排序C. 快速排序 D. 归并排序13.已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（ ）A. T[2] B. T[4]C. T[8] D. T[10]14.适宜进行批量处理的文件类型是（ ）A. 顺序文件 B. 索引顺序文件C. 散列文件 D. 多关键字文件15.VSAM文件的索引结构为（ ）A. B+树 B. 二叉排序树C. B-树 D. 最优二叉树二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.如果某算法对于规模为n的问题的时间耗费为T（n）=3n3，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的 倍。17.将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时间复杂度是 。18.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是 。19.字符串“sgabacbadfgbacst” 中存在有 个与字符串“ba”相同的子串。20.假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC（a00）,且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为 。21.假设用表示树的边（其中x是y的双亲），已知一棵树的边集为{,,,,,}，该树的度是 。22.n个顶点且含有环路的无向连通图中，至少含有 条边。23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 。24.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对 结构也无特殊要求。25.顺序文件中记录存放的物理顺序和 顺序一致。三、解答题(本大题共4小题，每小题5分，共20分)26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。前序序列：后序序列：27.图的邻接表的类型定义如下所示：#define MaxVertexNum 50typedef struct node {int adjvex;struct node *next;}EdgeNode;typedef struct {VertexType vertex;EdgeNode *firstedge;}VertexNode;typedef VertexNode AdjList[MaxVertexNum];typedef struct {AdjList adjlist;int n, e;}ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。题27图28.某类物品的编号由一个大写英文字母及2位数字（0..9）组成，形如E32。运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。E13，A37，F43，B32，B47，E12，F37，B12第一趟：第二趟：第三趟：29.（1）画出对表长为13的有序顺序表进行二分查找的判定树；（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。（1）（2）四、算法阅读题（本大题共4小题，每小题5分，共20分）30.已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态；（2）简述算法f30的功能。void f30 (SeqList *L) {int i,j;for (i=j=0;ilength; i++)if(L->data[i]>=0){if(i!=j)L->data[j]=L->data[i];j++；}L->length=j;}(1)(2)31.阅读下列算法，并回答问题：（1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f31 (&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态；（2）简述算法f31的功能。（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）void f31 (Queue*Q, Queue*Q1, Queue*Q2) {int e;lnitQueue (Q1);lnitQueue (Q2);while (!QueueEmpty (Q)) {e=DeQueue (Q);if (e>=0) EnQueue (Q1,e);else EnQueue (Q2,e)}}（1）（2）32.阅读下列算法，并回答问题：（1）假设串由合法的英文字母和空格组成，并以’\0’作结束符。设串s=”⊔⊔|⊔am⊔a⊔⊔⊔student”(⊔表示空格符)，写出f32（s）的返回值；（2）简述算法f32的功能。int f32 (char*s){int i, n, inword;n=inword=0;for (i=0;s[i]!=’\0’;i++)if (s[i]!=’⊔’&& inword==0){inword=1;n++;}else if (s[i]==’⊔’&& inword==1)inword=0;return n;}（1）（2）33.阅读下列对正整数关键字序列L操作的算法，并回答问题：（1）设L=(28,19,27,49,56,12,10,25,20,50),写出f33 (L,4)的返回值；（2）简述函数f33的功能。int Partition (SeqList*L, int low, int high);‖对L[low..high]做划分，返回基准记录的位置，并使左部的关键字‖都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字int f33 (SeqList L, int k){int low, high, pivotpos;low=1;high=L.length;if (khigh)return-1;do {pivotpos=Partition (&L, low, high);‖调用快速排序的划分算法if (pivotposk)high=pivotpos-1;}while (pivotpos!=k);return L.data [pivotpos];}（1）（2） 五、算法设计题（本题10分）34.二叉排序树的类型定义如下：typedef struct BSTNode {‖ 二叉排序树的结点结构int data; ‖数据域struct BSTNode *lchild, *rchild; ‖左、右孩子指针}BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。
第六题选B，因为完全二叉树的深度h满足：2^i-1=100；可以算出i=7时为128；
我就是学计算机网络专业的北京自考计算机网络（独立本科段） 课程代码 课程名称 学分 非笔试课程代码 非笔试课程名称 非笔试课程学分 备注 00004 毛泽东思想概论 2 00005 马克思主义政治经济学原理 3 00015 英语（二） 14 00023 高等数学（工本） 10 00420 物理（工） 5 00421 物理（工）（实验） 1 02194 工程经济 4 02314 模拟电路与数字电路 6 02315 模拟电路与数字电路（实验） 2 加考课 02142 数据结构导论 4 02319 微型计算机及其接口技术 2 02320 微型计算机及其接口技术（实验） 2 02384 计算机原理 4 02335 网络操作系统 5 02354 信号与系统 4 02355 信号与系统（实验） 1 02364 数据通信原理 5 02379 计算机网络管理 3 03137 计算机网络基本原理 7 03138 计算机网络基本原理实验 1 03139 数据库技术 4 03140 数据库技术（实验） 1 03141 局域网技术与组网工程 5 03142 互联网及其应用 4 03143 互联网及其应用（实验） 1 10032 计算机网络专业毕业设计（论文） 0 你说的网络工程专业好像没有，是不是通信工程专业？(01B0809)计算机通信工程（独立本科段） 课程代码 课程名称 学分 非笔试课程代码 非笔试课程名称 非笔试课程学分 备注 00004 毛泽东思想概论 2 00005 马克思主义政治经济学原理 3 00015 英语（二） 14 00023 高等数学（工本） 10 00420 物理（工） 5 00421 物理（工）（实验） 1 02197 概率论与数理统计（二） 3 02199 复变函数与积分变换 3 02326 操作系统 4 02327 操作系统（实验） 1 02331 数据结构 3 02332 数据结构（上机） 1 02336 数据库原理 4 02337 数据库原理（上机） 1 02338 光纤通信原理 4 02342 非线性电子电路 3 02343 非线性电子电路（实验） 1 加考课 02361 通信技术基础 4 02354 信号与系统 4 02355 信号与系统（实验） 1 02360 数字通信原理 4 02368 通信英语 4 02369 计算机通信接口技术 3 02370 计算机通信接口技术（上机） 1 02372 程控交换与宽带交换 5 02373 计算机通信网 4 02374 计算机通信网（上机） 1 02364 数据通信原理 5 10029 计算机通信工程专业毕业设计 0 不过如果你选择自学高考，选择理工科不是很容易，文科相对容易一些，相关专业可以参见这个网站。祝你好运！
【免费定制个人学历提升方案和复习资料： 】唐山学院是省内一本，省外二本。唐山学院地处河北省唐山市，是一所以工为主，经、管、文、法、艺等多学科协调发展的公办全日制普通本科院校。学院前身为1956年建校唐山市工业夜大学。1985年，西南交通大学致力支援唐山成立了唐山分校。2002年，西南交通大学唐山分校、唐山高等专科学校、唐山市职工大学三校合并组建唐山学院。2014年，河北科技大学唐山分院实质性并入唐山学院。2015年，唐山市对外经济贸易学校实质性并入唐山学院。2016年，学校成为河北省省级硕士立项建设单位。省内一本，省外二本下方免费学历提升方案介绍： 2013年10月自考02142数据结构导论真题试卷 格式：PDF大小：241.51KB 2015年04月自考00142计量经济学真题试卷 格式：PDF大小：359.8KB自考/成考考试有疑问、不知道自考/成考考点内容、不清楚自考/成考考试当地政策，点击底部咨询猎考网，免费获取个人学历提升方案：
先看一遍书，然后自己做练习，不会的翻书找答案，然后详细标注，这样有目的的学习，效果才好！
全国2009年1月高等教育自学考试数据结构试题课程代码02331答案急求。。谢谢。。最好答案和题都有。。尤其是答案。。谢谢啦。。
深度的递归算法int depth(BiTreeNode * T){ if(T==NULL) return 0; // 如果结点为空，高度为0 else { int h1= depth(T->lchild); // 获得左子树的高度 int h2= depth(T->rchild); // 获得右子树的高度 return max(h1,h2)+1; }}
全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; inext==head B. p->next->next==headC. p->next==NULL D. p==head4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ ）A. SXSSXXXX B. SXXSXSSXC. SXSXXSSX D. SSSXXSXX5.两个字符串相等的条件是（ ）A. 串的长度相等 B. 含有相同的字符集C. 都是非空串 D. 串的长度相等且对应的字符相同6.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（ ）A. head (tail (head (L))) B. head (head(head(L)))C. tail (head (tail (L))) D. head (head (tail (L)))7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）A. 0 B. 1C. 48 D. 498.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ）A. Dout B. Dout-1C. Dout+1 D. n9.如图所示的有向无环图可以得到的拓扑序列的个数是（ ）A. 3 B. 4C. 5 D. 610.如图所示的带权无向图的最小生成树的权为（ ）A. 51 B. 52C. 54 D. 5611.对长度为n的关键字序列进行堆排序的空间复杂度为（ ）A. O（log2n） B. O（1）C. O（n） D. O（n*log2n）12.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为（35，51，24，13，68，56，42，77，93）（35，24，13，51，56，42，68，77，93）所采用的排序方法是（ ）A. 插入排序 B. 冒泡排序C. 快速排序 D. 归并排序13.已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（ ）A. T[2] B. T[4]C. T[8] D. T[10]14.适宜进行批量处理的文件类型是（ ）A. 顺序文件 B. 索引顺序文件C. 散列文件 D. 多关键字文件15.VSAM文件的索引结构为（ ）A. B+树 B. 二叉排序树C. B-树 D. 最优二叉树二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.如果某算法对于规模为n的问题的时间耗费为T（n）=3n3，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的 倍。17.将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时间复杂度是 。18.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是 。19.字符串“sgabacbadfgbacst” 中存在有 个与字符串“ba”相同的子串。20.假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC（a00）,且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为 。21.假设用表示树的边（其中x是y的双亲），已知一棵树的边集为{,,,,,}，该树的度是 。22.n个顶点且含有环路的无向连通图中，至少含有 条边。23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 。24.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对 结构也无特殊要求。25.顺序文件中记录存放的物理顺序和 顺序一致。三、解答题(本大题共4小题，每小题5分，共20分)26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。前序序列：后序序列：27.图的邻接表的类型定义如下所示：#define MaxVertexNum 50typedef struct node {int adjvex;struct node *next;}EdgeNode;typedef struct {VertexType vertex;EdgeNode *firstedge;}VertexNode;typedef VertexNode AdjList[MaxVertexNum];typedef struct {AdjList adjlist;int n, e;}ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。题27图28.某类物品的编号由一个大写英文字母及2位数字（0..9）组成，形如E32。运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。E13，A37，F43，B32，B47，E12，F37，B12第一趟：第二趟：第三趟：29.（1）画出对表长为13的有序顺序表进行二分查找的判定树；（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。（1）（2）四、算法阅读题（本大题共4小题，每小题5分，共20分）30.已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态；（2）简述算法f30的功能。void f30 (SeqList *L) {int i,j;for (i=j=0;ilength; i++)if(L->data[i]>=0){if(i!=j)L->data[j]=L->data[i];j++；}L->length=j;}(1)(2)31.阅读下列算法，并回答问题：（1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f31 (&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态；（2）简述算法f31的功能。（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）void f31 (Queue*Q, Queue*Q1, Queue*Q2) {int e;lnitQueue (Q1);lnitQueue (Q2);while (!QueueEmpty (Q)) {e=DeQueue (Q);if (e>=0) EnQueue (Q1,e);else EnQueue (Q2,e)}}（1）（2）32.阅读下列算法，并回答问题：（1）假设串由合法的英文字母和空格组成，并以’\0’作结束符。设串s=”⊔⊔|⊔am⊔a⊔⊔⊔student”(⊔表示空格符)，写出f32（s）的返回值；（2）简述算法f32的功能。int f32 (char*s){int i, n, inword;n=inword=0;for (i=0;s[i]!=’\0’;i++)if (s[i]!=’⊔’&& inword==0){inword=1;n++;}else if (s[i]==’⊔’&& inword==1)inword=0;return n;}（1）（2）33.阅读下列对正整数关键字序列L操作的算法，并回答问题：（1）设L=(28,19,27,49,56,12,10,25,20,50),写出f33 (L,4)的返回值；（2）简述函数f33的功能。int Partition (SeqList*L, int low, int high);‖对L[low..high]做划分，返回基准记录的位置，并使左部的关键字‖都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字int f33 (SeqList L, int k){int low, high, pivotpos;low=1;high=L.length;if (khigh)return-1;do {pivotpos=Partition (&L, low, high);‖调用快速排序的划分算法if (pivotposk)high=pivotpos-1;}while (pivotpos!=k);return L.data [pivotpos];}（1）（2） 五、算法设计题（本题10分）34.二叉排序树的类型定义如下：typedef struct BSTNode {‖ 二叉排序树的结点结构int data; ‖数据域struct BSTNode *lchild, *rchild; ‖左、右孩子指针}BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。
hgkghkghkghkghk
《数据结构》试题一、选择题（每小题2分，共30分）1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A、单链表 B、双链表 C、单向循环 D、顺序表2． 串是任意有限个（ ）A、符号构成的序列 B、符号构成的集合C、字符构成的序列 D、字符构成的集合3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足：aij≠0(i≥j, l≤i, j≤ 10)aij=0 (i。( )i6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( )7．“顺序查找法”是指在顺序表上进行查找的方法。（ ）8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）9．键值序列{A，C，D，E，F，E，F}是一个堆。10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（） 三、填空题（每小题2分，共20分）1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；2．有一个长度为20的有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找长度为3。3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为＿＿＿＿＿。若A的初始状态为递减排列，则记录的交换次数为＿＿＿＿＿＿＿。4．在无头结点的双链表中，指针P所指结点是第一个结点的条件是＿＿＿＿＿＿。5．G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是＿＿＿＿＿图。6．如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。7．深度为8（根的层次号为1）的满二叉树有＿＿＿＿＿＿个叶子结点。 8．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为＿＿＿＿＿＿＿。9．设某闭散列表HT未满，散列函数H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。void printword(keytype HT[m]) { for(i=1;i<=26;i++) { j=i; while(____________________) { if (____________________) printf(“datatype”,HT[j]); j=(j+1)% m; } } }10．设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p)；p->data=x; p->next=NULL；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； 四、简答题：（每小题4分，共20分）1. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？3. 设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？4. 在KMP算法中，已知模式串为ADABCADADA ，请写出模式串的next[j]函数值。5. 中序遍历的递归算法平均空间复杂度为多少？ 五、 算法设计题（每小题10分，共20分）1. 试编写一个算法，判断一给定的整型数组a[n]是不是一个堆。2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。参考答案一、选择题1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C 13、B14、C15、D二、判断题 1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. × 三、填空题1．U=L - > next2．4。3．n-1、n(n-1)/2。4．p - > prior = NULL。5．连通6．回路或环7．28-1 = 27 = 1288．249．HT[j]!=NULL或HT[j]不为空、H(HT[j])=I10．rear - > next = p、rear = p四、简答题：1. 答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。2.答：是：ABDEGCFH3. 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)； 即O（1000log21000）=O(10000) 锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）4. 答： 01121123435. 答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为O(log2n) 五、 算法设计题1.解：提示：堆的定义是：kia[2*i]|| a[i]>a[2*i+1])return(-1);return(minleap)};else { for( i=1; i<=n/2; i++) if (a[i]lchild) EnQueue(Q,{r.node->lchild, r.layer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1}); } //按层序入队时要随时标注结点所在层号 h=r.layer; //最后一个队列元素所在层就是树的高度 for(maxn=count[0], i=1; h; i++) if(count[i]>maxn) maxn=count[i]; //求出哪一层结点数最多 return (h*maxn)} // Width
1.同22. C．教科书第一页，绪论1.1基本术语..........数据元素是数据的基本单位， 数据项是构成数据元素的不可分割的具有独立含义的最小标识单位 、3.B插入和删除最好的和最坏的时间复杂度是O（1），O(n).品均时间复杂度是O(n);4.B5.B6.详情请看数据结构实用教程c语言版的教材第86页，具有相同的逻辑结构（都是线性表） 可以采用相同的存储方法（顺序存储，链接存储）具有不同的运算特点栈是后进先出，队列是先进先出。8.b//79页12.有向图顶点与边的关系是n(n-1)，无向图是n(n-1)/2,13.无向图中一个顶点的度是指与该顶点相关的边的条数，同（路径）14.C15.D16.217.18.Push pop