数据结构笔试题和答案
数据结构笔试题和答案：
1. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：
q=head;
while (q->next!=p) q=q->next;
s= new Node; s->data=e;
q->next= ; //填空
s->next= ; //填空
2. 线性表的顺序存储结构是一种 的存储结构，而链式存储结构是一种___的存储结构。
A.随机存取 B.索引存取 C.顺序存取 D.散列存取
3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。
A. 必须是连续的 B. 部分地址必须是连续的
C. 一定是不连续的 D. 连续或不连续都可以
4. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。
A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p;
C. q->next=s; s->next=p; D. p->next=s; s->next=q;
5. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。
A. s->next=p; p->next=s; B. s->next=p->next; p->next=s;
C. s->next=p->next; p=s; C. p->next=s; s->next=p;
6. 在一个单链表中，若删除p所指结点的后续结点，则执行____。
A. p->next= p->next->next; B. p= p->next; p->next= p->next->next;
C. p->next= p->next; D. p= p->next->next;
7. 链表不具备的特点是 ____ 。
A 可随机访问任何一个元素 B 插入、删除操作不需要移动元素
C 无需事先估计存储空间大小 D 所需存储空间与线性表长度成正比
8. 以下关于线性表的说法不正确的是 。
A 线性表中的`数据元素可以是数字、字符、记录等不同类型。
B 线性表中包含的数据元素个数不是任意的。
C 线性表中的每个结点都有且只有一个直接前趋和直接后继。
D 存在这样的线性表：表中各结点都没有直接前趋和直接后继。
9. 在一个长度为n的顺序表中删除第i个元素，要移动 个元素。如果要在第i个元素前插入一个元素，要后移( )个元素。 N-I N-I+1
答案
1.q->next=s;
s->next=p;
2.A/C(这题是考察对概念的理解，可参考第7题，“顺序表才能随即存取，而链表不可以”)
3.D
4.C
5.B
6.A
7.A(此题绝对选A，因为链表只能根据他的前一个结点才能找到下一个结点，不具备随即访问元素的功能)
8.C
9.n-i; n-i+1
更多的相关笔试题目推荐：
融捷科java软件工程师技笔试题 运营维护工程师笔试题 中国银行计算机方向笔试题目
第六题选B，因为完全二叉树的深度h满足：2^i-1=100；可以算出i=7时为128；
全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; i
全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; i
一 单项选择题(本大题共 小题 每小题 分 共 分)
在每小题列出的四个备选项中只有一个是符合题目要求的 请将其代码填写在题后的括号内 错选 多选或未选均无分
在数据结构中 数据的逻辑结构可以分成()
A 内部结构和外部结构 B 线性结构和非线性结构
C 紧凑结构和非紧揍结构 D 动态结构和静态结构
在以单链表为存储结构的线性表中 数据元素之间的逻辑关系用()
A 数据元素的相邻地址表示 B 数据元素在表中的序号表示
C 指向后继元素的指针表示 D 数据元素的值表示
设 p 指向单链表中的一个结点 s 指向待插入的结点 则下述程序段的功能是()
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 之前插入结点 *s
栈和队列都是()
A 限制存取位置的线性结构 B 顺序存储的线性结构
C 链式存储的线性结构 D 限制存取位置的非线性结构
若数组 s[ n ] 为两个栈 s 和 s 的共用存储空间 且仅当 s[ n ] 全满时 各栈才不能进行进栈操作 则为这两个栈分配空间的最佳方案是 s 和 s 的栈顶指针的初值分别为()
A 和 n+ B 和 n/
C 和 n D 和 n+
执行下列程序段后 串 X 的值为()
S= 〞 abcdefgh 〞 ; T= 〞 xyzw 〞 ;
substr (X S strlen(T));
substr (Y S stelen(T) );
strcat (X Y);
A 〞 cdefgh 〞 B 〞 cdxyzw 〞
C 〞 cdefxy 〞 D 〞 cdefef 〞
多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为()
A 数组的元素处在行和列两个关系中 B 数组的元素必须从左到右顺序排列
C 数组的元素之间存在次序关系 D 数组是多维结构 内存是一维结构
从广义表 LS =( (p q) r s )中分解出原子 q 的运算是()
A tail (head (LS)) B head (tail (head (LS)))
C head (tail (LS)) D tail (tail (head (LS)))
在具有 n 个叶子结点的严格二叉树中 结点总数为()
A n+ B n
C n D n
若 是有向图的一条边 则称()
A v i 邻接于 v j B v j 邻接于 v i
C v i 和 v j 相互邻接 D v i 与 v j 不相邻接
在一个带权连通图 G 中 权值最小的边一定包含在 G 的()
A 最小生成树中 B 深度优先生成树中
C 广度优先生成树中 D 深度优先生成森林中
当在二叉排序树中插入一个新结点时 若树中不存在与待插入结点的关键字相同的结点 且新结点的关键字小于根结点的关键字 则新结点将成为()
A 左子树的叶子结点 B 左子树的分支结点
C 右子树的叶子结点 D 右子树的分支结点
希尔排序的增量序列必须是()
A 递增的 B 随机的
C 递减的 D 非递减的
如果在排序过程中 每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置 则该排序方法称为()
A 插入排序 B 归并排序
C 冒泡排序 D 堆排序
设置溢出区的文件是()
A 索引非顺序文件 B ISAM 文件
C VSAM 文件 D 顺序文件
二 填空题(本大题共 小题 每小题 分 共 分)
请在每小题的空格中填上正确答案 错填 不填均无分
下列程序段的时间复杂度为 ________________
product = ;
for (i = n;i> ; i )
for (j = i+ ; j product *=j; 17 .已知指针 p 指向单链表中某个结点，则语句 p -> next =p -> next -> next 的作用是 ________________ 。WiNGwit. 18 .假设元素只能按 a,b,c,d 的顺序依次进栈，且得到的出栈序列中的第一个元素为 c ，则可能得到的出栈序列为 ________________ ，不可能得到的出栈序列为 ________________ 。 19 .若链串结点中的指针占 4 个字节，每个字符占 1 个字节，则结点大小为 2 的链串的存储密度为 ________________ 。 20 .右图表示的广义表为 ________________ 。 21 .若一棵满三叉树中含有 121 个结点，则该 树的深度为 ________________ 。 22 .若以邻接矩阵表示有向图，则邻接矩阵上 第 i 行中非零元素的个数即为顶点 v i 的 ________________ 。 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 。 如果用 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 的操作步骤。 27 .已知树如右图所示， ( 1 )写出该树的后序序列; ( 2 )画出由该树转换得到的二叉树。 28 .为关键字( 17 ， 33 ， 31 ， 40 ， 48 )构造一个长度为 7 的散列表，设散列函数为 h(key)=key%7, 用开放定址法解决冲突的探查序列是 hi = (h(key) + i(key%5+1))%7 0 ≤ i ≤ 6 ( 1 )画出构造所得的散列表; ( 2 )求出在等概率情况下查找成功时的平均查找长度。 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 mid, 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 )第五次调用时的参数值; 四、算法阅读题(本大题共 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) (2) (3) 全国2006年10月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.数据的基本单位是（ ）A.数据项 B.数据类型 C.数据元素 D.数据变量2.下列程序的时间复杂度为（ ）i=0；s=0；while（s 一 单项选择题(本大题共 小题 每小题 分 共 分 在每小题的四个备选答案中 选出一个正确答案 并将正确答案的序号填在题干的括号内) 下面程序段的时间复杂度是( ) for(i= ;i for(j=1;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的后继”的语句是( ) 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,则( ) A.p指向头结点 B.p指向尾结点 C.*p的直接后继是头结点 D.*P的直接后继是尾结点 4.判定“带头结点的链队列为空”的条件是( ) A.Q.front==NULL B.Q.rear==NULL C.Q.front==Q.rear D.Q.front!=Q.rear 5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( ) A.联接 B.求子串 C.字符定位 D.子串定位 6.广义表A=(a,(b),(),(c,d,e))的长度为( ) A.4 B.5 C.6 D.7 7.一棵含18个结点的二叉树的高度至少为( ) A.3 B.4 C.5 D.6 8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 9.无向图中一个顶点的度是指图中( ) A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数 C.通过该顶点的回路数 D.与该顶点连通的顶点数 10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( ) 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)且空间性能最好的是( ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。.WingwIT.CoM对这些子序列进行一趟两两归并的结果是( ) 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块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( ) A.21 B.23 C.41 D.62 14.索引非顺序文件的特点是( ) A.主文件无序，索引表有序 B.主文件有序，索引表无序 C.主文件有序，索引表有序 D.主文件无序，索引表无序 15.倒排文件的主要优点是( ) A.便于进行插入和删除运算 B.便于进行文件的恢复 C.便于进行多关键字查询 D.节省存储空间 二、填空题 (本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 16.抽象数据类型的特点是将____________和____________封装在一起，从而现实信息隐藏。 17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。 18.在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。 19.如图两个栈共享一个向量空间，top1和top分别为指向两个栈顶元素的指针，则“栈满”的判定条件是____________。 20.设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是____________。 21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是____________。 22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为____________。 23.能够成功完全拓扑排序的图一定是一个____________。 24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用____________较为适当。 25.假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为____________。 三、解答题 (本大题共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) (2) (3) 31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题： (1)写出执行函数调用f(p)的输出结果; (2)简述函数f的功能。 { while(t) { printf(t->data); if(t->lchild) t=t->lchild; else t=t->rchild; } } (1) (2) 32.下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点v i 的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点v k 的下一个顶点是v j 。请在空缺处填入合适的内容，使其成为一个完整的算法。 vertex firstedge 已知邻接表的顶点表结点结构为： adjvex next 边表结点 EdgeNode结构为： int cycle_path[MaxNum]; int FindCycle(ALGraph*G,int i) {//若回路存在，则返回1，否则返回0 int j; for(j=0;j 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) 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 strcut node{strcut node1{char a ;node1 *next ;}node1;strcut node2{int a ;node2 *next ;}node2;strcut node3{long a ;node3 *next ;}node3;}node;用这个结构体就可以解决你要的问题了L1 = node.node1.next;L2 = node.node2.next;L3 = node.node3.next; 如果对您有帮助，请记得采纳为满意答案，谢谢！祝您生活愉快！ vaela 呵呵，你算找对人了！答案不是很多，但试题很多的。我发到你消息里了！ 2009年1月自考数据库及其应用试题 2009年1月自考数据库及其应用试题 课程代码：02120 一、单项选择题(本大题共20小题。每小题2分，共40分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.有关系模式：R(课程编号，课程名称，教师编号，教师姓名，授课班级)，若一名教师可讲授多门课程，一门课程可由多名教师讲授，则R属于( )...... 全国2008年10月自学考试数据库及其应用试题 全国2008年10月自学考试数据库及其应用试题 课程代码：02120 一、单项选择题(本大题共20小题，每小题2分，共40分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.Access中的查询对象属于数据库的( ) A.概念模型 B.外部模型 C.内部模型 D.逻辑模型 2.在下列...... 2008年1月全国自考试题数据库及其应用试卷 全国2008年1月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题（本大题共20小题，每小题2分，共40分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．E-R模型属于数据库的（ ） A．概念模型 B．逻辑模型 C．内部模型 D．外部模型 2．实体完整性...... 2007年10月自考试题数据库及其应用试卷 全国2007年10月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题（本大题共20小题，每小题2分，共40分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．关系模型中，实现实体之间联系是通过（ ） A．关系 B．指针 C．表 D．公共字段 2．数据完整性...... 全国2007年1月高等教育自学考试数据库及其应用试题历年试卷 全国2007年1月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题（本大题共20小题，每小题2分，共40分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.若关系模式R属于1NF，且所有非主属性都完全函数依赖于R的主键。则R属于( ) A.1...... 全国2006年10月高等教育自学考试数据库及其应用试题历年试卷 全国2006年10月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题（本大题共20小题，每小题2分，共40分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．以下不属于数据库技术特点的是（ ） A．数据结构化 B．数据共享 C．数据冗余小 D．以...... 全国2006年1月高等教育自学考试数据库及其应用试题历年试卷 全国2006年1月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题（本大题共20小题，每小题2分，共40分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.以下不是数据库技术所具备的特点是（ ） A.数据结构化 B.数据冗余小 C.有较高的...... 2005年10月自考试卷数据库及其应用 2005年10月自考试卷数据库及其应用 ...... 2005年10月数据库及其应用试题答案 2005年10月数据库及其应用试题答案 ...... 浙江省2005年10月高等教育自学考试数据库及其应用试题历年试卷 全国2005年10月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题（本大题共20小题，每小题2分，共40分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.文件系统方式管理数据有很多缺陷，以下不是文件方式缺陷的是（ ） A.数据联系弱 B.数...... 全国2005年1月高等教育自学考试数据库及其应用试题历年试卷 全国2005年1月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题（本大题共20小题，每小题2分，共40分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列关于“联系”的描述，正确的是（ ） A．联系不是实体，也没有属性 B．联系是实体，但没有属性 全国2004年10月高等教育自学考试数据库及其应用试题历年试卷 全国2004年10月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题（本大题共20小题，每小题2分，共40分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.数据管理技术发展所经历的过程是：( ) A.数据库—文件系统—自由管理 B.文件系统—自由...... 2004年10月自考数据库及其应用试卷参考答案 更多试卷答案下载 免费试听网校课程 2004年10月自考数据库及其应用试卷参考答案 一、l．C 2．D 3．B 4．C 5．B 6．B 7．B 8．C 9．C l0．B ll．C l2．D 13．B l4。B l5．B l 6．B 17．B l8．A l9．D 20．A 35．(1)书名=“线性代数” 浙江省2004年7月高等教育自学考试数据库及其应用试题历年试卷 浙江省2004年7月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题（本大题共20小题，每小题2分，共40分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.按照数据模型，FoxPro是（ ）。 A.层次型数据库管理系统 B.网状型数据库管理系统 ...... 浙江省2004年4月高等教育自学考试数据库及其应用试题历年试卷 浙江省2004年4月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共20分) 1.在下列计算机表示的信息中，不能称为“数据”的是（ ）。 A.股票名称 B.股票曲线图 C.电脑软件 D.音乐编码 2....... 浙江省2004年1月高等教育自学考试数据库及其应用试题历年试卷 浙江省2004年1月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题2分，共30分) 1.下述关于数据库系统的正确叙述是：（ ） A. 数据库系统避免了一切冗余 B. 数据库系统中数据的一致性是指数据类型一致 全国2003年10月高等教育自学考试数据库及其应用试题历年试卷 全国2003年10月高等教育自学考试 数据库及其应用试题 课程代码：02120 第一部分 选择题（共40分） 一、单项选择题(本大题共20小题，每小题2分，共40分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．在文件系统中有关数据项、记录、文件的正确描述是( ) A.文...... 浙江省2003年7月高等教育自学考试数据库及其应用试题历年试卷 浙江省2003年7月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题2分，共30分) 1.foxpro系统所用的术语与关系术语存在以下对应关系( )。 A.库结构对应关系，库文件对应元组，记录对应属性，字段对应属性值 B.库结...... 浙江省2003年4月高等教育自学考试数据库及其应用试题历年试卷 浙江省2003年4月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共20分) 1.下列最容易用计算机符号表示的数据是( )。 A.人的姓名 B.人的声音 C.人的动作 D.计算机程序 全国2003年1月高等教育自学考试数据库及其应用试题历年试卷 全国2003年1月高等教育自学考试 数据库及其应用试题 课程代码：02120 第一部分 选择题 (共40分) 一、单项选择题(本大题共20小题，每小题2分，共40分)在每小题列出的四个选项中只有一个是符合题目要求的。请将其代码填在题后的括号内。错选或未选均无分。 1.在数据库系统中，面向用户、也就是用户所涉及的数据库被称为( ) A.外模...... 全国2002年10月高等教育自学考试数据库及其应用试题历年试卷 全国2002年10月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题(在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。每小题2分，共40分) 1.英文缩写DBA代表( ) A.数据库管理员 B.数据库管理系统 C.数据定义语言 ...... 浙江省2002年1月高等教育自学考试数据库及其应用试题历年试卷 浙江省2002年1月高等教育自学考试 数据库及其应用试题 课程代码：02120 一、单项选择题(在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。每小题1分，共20分) 1.描述在外部存储器上如何组织数据的是( ) A.用户模式 B.模式 C.外模式 D.内模式 2.应用...... 浙江省2002年1月自考数据库及其应用答案 更多试卷答案下载 免费试听网校课程 浙江省2002年1月自考数据库及其应用答案 课程代码：02120 一、单项选择题(每小题1分，共20分) 1.D 2.D 3.A 4.B 5.B 6.A 7.C 8.B 9.A ...... 浙江省2001年10月自学考试数据库及其应用试题 更多试卷答案下载 免费试听网校课程 浙江省2001年10月自学考试数据库及其应用试题 课程代码：02120 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共20分) 1.要保证数据库物理数据独立性，需要修改的是( ) A.模式 B.模式与内模...... 浙江省2001年10月自考数据库及其应用试题参考答案 更多试卷答案下载 免费试听网校课程 浙江省2001年10月自考数据库及其应用试题参考答案 课程代码：02120 一、单项选择题(每小题1分，共20分) 1.B 2.D 3.D 4.D 5.C 6.A 7.A 8.B 9.D ...... 2000年10月自考数据库及应用答案 2000年10月自考自学考试数据库及应用答案 一、单项选择题（本大题共10小题，每小题1分，共10分） 1.A 3.D 5.B 7.C 9.D 2.B 4.D 6.D 8.A 10.D 二、多项选择题（本大题共5小题，每小题2分，共10分） 11.ABCD 12.BCD 13.BD 14.ABC 15.ABCDE 三、填空题（本...... 2000年10月自考数据库及应用试题试卷真题 2000年10月数据库及应用试卷和答案 第一部分 选择题 一、单项选择题(本大题共10小题，每小题1分，共10分) 在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1、三级模式间存在两种映射，它们是( ) A．模式与子模式间，模式与内 可以转发一份给我吗，谢谢 一 单项选择题(本大题共 小题 每小题 分 共 分 在每小题的四个备选答案中 选出一个正确答案 并将正确答案的序号填在题干的括号内) 下面程序段的时间复杂度是( ) for(i= ;i for(j=1;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的后继”的语句是( ) 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,则( ) A.p指向头结点 B.p指向尾结点 C.*p的直接后继是头结点 D.*P的直接后继是尾结点 4.判定“带头结点的链队列为空”的条件是( ) A.Q.front==NULL B.Q.rear==NULL C.Q.front==Q.rear D.Q.front!=Q.rear 5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( ) A.联接 B.求子串 C.字符定位 D.子串定位 6.广义表A=(a,(b),(),(c,d,e))的长度为( ) A.4 B.5 C.6 D.7 7.一棵含18个结点的二叉树的高度至少为( ) A.3 B.4 C.5 D.6 8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 9.无向图中一个顶点的度是指图中( ) A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数 C.通过该顶点的回路数 D.与该顶点连通的顶点数 10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( ) 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)且空间性能最好的是( ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。.WingwIT.CoM对这些子序列进行一趟两两归并的结果是( ) 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块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( ) A.21 B.23 C.41 D.62 14.索引非顺序文件的特点是( ) A.主文件无序，索引表有序 B.主文件有序，索引表无序 C.主文件有序，索引表有序 D.主文件无序，索引表无序 15.倒排文件的主要优点是( ) A.便于进行插入和删除运算 B.便于进行文件的恢复 C.便于进行多关键字查询 D.节省存储空间 二、填空题 (本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 16.抽象数据类型的特点是将____________和____________封装在一起，从而现实信息隐藏。 17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。 18.在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。 19.如图两个栈共享一个向量空间，top1和top分别为指向两个栈顶元素的指针，则“栈满”的判定条件是____________。 20.设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是____________。 21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是____________。 22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为____________。 23.能够成功完全拓扑排序的图一定是一个____________。 24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用____________较为适当。 25.假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为____________。 三、解答题 (本大题共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) (2) (3) 31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题： (1)写出执行函数调用f(p)的输出结果; (2)简述函数f的功能。 { while(t) { printf(t->data); if(t->lchild) t=t->lchild; else t=t->rchild; } } (1) (2) 32.下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点v i 的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点v k 的下一个顶点是v j 。请在空缺处填入合适的内容，使其成为一个完整的算法。 vertex firstedge 已知邻接表的顶点表结点结构为： adjvex next 边表结点 EdgeNode结构为： int cycle_path[MaxNum]; int FindCycle(ALGraph*G,int i) {//若回路存在，则返回1，否则返回0 int j; for(j=0;j 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) 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 《数据结构》期末考试试卷（ A ）一、 选择题（每小题2分，共24分）1．计算机识别、存储和加工处理的对象被统称为( A )A.数据 B.数据元素C.数据结构 D.数据类型2．栈和队列都是（ A ）A．限制存取位置的线性结构 B．顺序存储的线性结构C．链式存储的线性结构 D．限制存取位置的非线性结构 3．链栈与顺序栈相比，比较明显的优点是( D )A.插入操作更加方便 B.删除操作更加方便C.不会出现下溢的情况 D.不会出现上溢的情况4．采用两类不同存储结构的字符串可分别简称为( B )A.主串和子串 B.顺序串和链串C.目标串和模式串 D.变量串和常量串5． 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：BA. 110 B .108C. 100 D. 120 6．串是一种特殊的线性表，其特殊性体现在：BA.可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为： CA. 2h B .2h-1C. 2h+1 D. h+1软件开发网 www.mscto.com8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ AA. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对9．一个有n个顶点的无向图最多有多少边？CA. n B .n(n-1)C. n(n-1)/2 D. 2n10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?CA. 1/2 B .1C. 2 D. 4 11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ A ）A．左子树的叶子结点 B．左子树的分支结点C．右子树的叶子结点 D．右子树的分支结点软件开发网 www.mscto.com12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )A.35和41 B.23和39C.15和44 D.25和51 二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分）原理见课本128页三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分) 深度优先；C0-C1-C3-C4-C5-C2宽度优先：C0-C1-C2-C3-C4-C5四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分）原理见课本250页五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查找关键字值12，93，166的过程。并写出二分查找的算法。（20分）0 1 2 3 4 5 6 7 812 23 45 66 76 88 93 103 166过程：mid=(0+8)/2=4high=3,low=0 mid=1high=0,low=0 mid=0（找到12）high=8,low=5,mid=6（找到93）high=8,low=7,mid=7high=8 low=8 mid=8算法：见课本84页上六、知单链表的结点结构为Data next下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。请在空缺处填入合适的内容，使其成为完整的算法。 (可用文字说明该算法的基本思想及执行的过程，10分)void SelectSort(LinkedList L){ LinkedList p,q,min; DataType rcd; p= (1) ; while(p!=NULL) { min=p; q=p->next; while(q!=NULL){ if( (2) )min=q; q=q->next; } if( (3) ){ rcd=p->data; p->data=min->data; min->data=rcd; } (4) ; }} 本题不会。嘿嘿。。。。七、一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分) 输入：四个基本性质：1.输入：有零个或多个有外部提供的量作为算法的输入 2：输出：算法产生至少一个量作为输出 3.：确定性：组成算法的每条指令是清晰的，无歧异的。 4.：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的八、何谓队列的"假溢"现象？如何解决？（5分）队列的假溢现象是指数组实现的顺序队列中，队尾指针已到达数组的下表上界产生上溢而队头指针之前还有若干 空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间的首尾相连。 九、说明并比较文件的各种物理结构。（6分） 链式存储结构的特点是借助_指示数据元素地址的指针______来表示数据元素之间的逻辑关系。数据的存储结构是其逻辑结构在计算机中的___存放形式________。 一 单项选择题(本大题共 小题 每小题 分 共 分 在每小题的四个备选答案中 选出一个正确答案 并将正确答案的序号填在题干的括号内) 下面程序段的时间复杂度是( ) for(i= ;i for(j=1;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的后继”的语句是( ) 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,则( ) A.p指向头结点 B.p指向尾结点 C.*p的直接后继是头结点 D.*P的直接后继是尾结点 4.判定“带头结点的链队列为空”的条件是( ) A.Q.front==NULL B.Q.rear==NULL C.Q.front==Q.rear D.Q.front!=Q.rear 5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( ) A.联接 B.求子串 C.字符定位 D.子串定位 6.广义表A=(a,(b),(),(c,d,e))的长度为( ) A.4 B.5 C.6 D.7 7.一棵含18个结点的二叉树的高度至少为( ) A.3 B.4 C.5 D.6 8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 9.无向图中一个顶点的度是指图中( ) A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数 C.通过该顶点的回路数 D.与该顶点连通的顶点数 10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( ) 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)且空间性能最好的是( ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。.WingwIT.CoM对这些子序列进行一趟两两归并的结果是( ) 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块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( ) A.21 B.23 C.41 D.62 14.索引非顺序文件的特点是( ) A.主文件无序，索引表有序 B.主文件有序，索引表无序 C.主文件有序，索引表有序 D.主文件无序，索引表无序 15.倒排文件的主要优点是( ) A.便于进行插入和删除运算 B.便于进行文件的恢复 C.便于进行多关键字查询 D.节省存储空间 二、填空题 (本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 16.抽象数据类型的特点是将____________和____________封装在一起，从而现实信息隐藏。 17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。 18.在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。 19.如图两个栈共享一个向量空间，top1和top分别为指向两个栈顶元素的指针，则“栈满”的判定条件是____________。 20.设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是____________。 21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是____________。 22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为____________。 23.能够成功完全拓扑排序的图一定是一个____________。 24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用____________较为适当。 25.假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为____________。 三、解答题 (本大题共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) (2) (3) 31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题： (1)写出执行函数调用f(p)的输出结果; (2)简述函数f的功能。 { while(t) { printf(t->data); if(t->lchild) t=t->lchild; else t=t->rchild; } } (1) (2) 32.下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点v i 的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点v k 的下一个顶点是v j 。请在空缺处填入合适的内容，使其成为一个完整的算法。 vertex firstedge 已知邻接表的顶点表结点结构为： adjvex next 边表结点 EdgeNode结构为： int cycle_path[MaxNum]; int FindCycle(ALGraph*G,int i) {//若回路存在，则返回1，否则返回0 int j; for(j=0;j 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) 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 全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; i 一 单项选择题(本大题共 小题 每小题 分 共 分 在每小题的四个备选答案中 选出一个正确答案 并将正确答案的序号填在题干的括号内) 下面程序段的时间复杂度是( ) for(i= ;i for(j=1;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的后继”的语句是( ) 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,则( ) A.p指向头结点 B.p指向尾结点 C.*p的直接后继是头结点 D.*P的直接后继是尾结点 4.判定“带头结点的链队列为空”的条件是( ) A.Q.front==NULL B.Q.rear==NULL C.Q.front==Q.rear D.Q.front!=Q.rear 5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( ) A.联接 B.求子串 C.字符定位 D.子串定位 6.广义表A=(a,(b),(),(c,d,e))的长度为( ) A.4 B.5 C.6 D.7 7.一棵含18个结点的二叉树的高度至少为( ) A.3 B.4 C.5 D.6 8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 9.无向图中一个顶点的度是指图中( ) A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数 C.通过该顶点的回路数 D.与该顶点连通的顶点数 10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( ) 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)且空间性能最好的是( ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。.WingwIT.CoM对这些子序列进行一趟两两归并的结果是( ) 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块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( ) A.21 B.23 C.41 D.62 14.索引非顺序文件的特点是( ) A.主文件无序，索引表有序 B.主文件有序，索引表无序 C.主文件有序，索引表有序 D.主文件无序，索引表无序 15.倒排文件的主要优点是( ) A.便于进行插入和删除运算 B.便于进行文件的恢复 C.便于进行多关键字查询 D.节省存储空间 二、填空题 (本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 16.抽象数据类型的特点是将____________和____________封装在一起，从而现实信息隐藏。 17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。 18.在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。 19.如图两个栈共享一个向量空间，top1和top分别为指向两个栈顶元素的指针，则“栈满”的判定条件是____________。 20.设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是____________。 21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是____________。 22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为____________。 23.能够成功完全拓扑排序的图一定是一个____________。 24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用____________较为适当。 25.假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为____________。 三、解答题 (本大题共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) (2) (3) 31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题： (1)写出执行函数调用f(p)的输出结果; (2)简述函数f的功能。 { while(t) { printf(t->data); if(t->lchild) t=t->lchild; else t=t->rchild; } } (1) (2) 32.下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点v i 的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点v k 的下一个顶点是v j 。请在空缺处填入合适的内容，使其成为一个完整的算法。 vertex firstedge 已知邻接表的顶点表结点结构为： adjvex next 边表结点 EdgeNode结构为： int cycle_path[MaxNum]; int FindCycle(ALGraph*G,int i) {//若回路存在，则返回1，否则返回0 int j; for(j=0;j 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) 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 这里有你想要的一切... 全国2010年4月自学考试计算机网络安全试题及答案全国2009年7月自考计算机网络安全试卷及答案全国2010年4月自学考试计算机网络安全试题及答案 备注：以上两套真题答案由杨尚杰为你亲情制作.自考乐园俱乐部全网首发..★★★欢迎下载...欢迎交流...其他：2010自考计算机网络安全串讲习题(燕园试题)自考计算机网络安全教材(高清扫描版)计算机网络安全超强笔记-------请到自考乐园俱乐部下载如果你还想找更多关于自考计算机网络安全的资料（比如笔记，课后答案...等等）...也欢迎你自己去这个俱乐部找找...一定会得到意想不到的收获...--------------------------------------------------------这里也许更适合你.... 百度贴吧：自考乐园俱乐部 自我感觉自考乐园俱乐部最适合你... 本人也是自考计算机网络（独立本科），和你也有类似想法...偶然间发现原来竟然有这样一个圈子：自考乐园俱乐部这里几乎聚集了最多的自考计算机网络独立本科的朋友，和几乎全部自考本专业的资料（更可贵的是还能免费下载...）也欢迎你和我们一起加入这个圈子... ------------------------------------------以下是这个俱乐部的简介：☆自考乐园---心境随缘，诚与天下自考人共勉！！！ ☆自考乐园---分享快乐，你的快乐老家！！！ ☆自考乐园---引领成功，你的精神乐园！！！-------------------------------------- ☆★☆与千万自考生同行，你准备好了吗?你希望在自考的征途中，有一群和你志同道合的人同行？ 你愿意在漫长的自考岁月中，有一群人和你分享快乐，分担忧愁吗？ 你渴望在一个人奋斗时，有一群人在背后默默支持你吗？ 你是否也一直在苦苦寻找这样一个平台，一群志同道合的人，一片积极向上的心，一个共同的追求，一个诚挚的鼓励，一个坚实的支持......对！！！就是这里！！！这里有你想要的一切...... 与志者同行，你也将成为志者！！！与成功者同行，你也将获得成功！！！与千万自考生同行，你准备好了吗？？？与千万自考生同行，你做好了准备吗？？？ 今天我们诚挚的发出邀请，真诚的欢迎广大报考和我相同专业的考生加入本俱乐部，一起交流，进步，提高.......我们正寻找特别的你亲情加入......... ---------------------------------我也认为百度贴吧：自考乐园俱乐部最好.......尤其是他们所共享的自考资料...几乎可以说是网上最全面，最系统的...加入自考乐园俱乐部...绝对会让你受益多多... 以下仅例举几科资料：●★自考乐园发帖须知★● ●自考乐园优秀主题简介● [置顶] 【资料整理】自考中国近现代史纲一贴通（资料大全） [精品] 【资料整理】自考马克思主义基本原理概论一贴通（资料大全） [精品] 【资料整理】自考计算机网络原理一贴通（资料大全） [精品] 【资料整理】自考Java语言程序设计(一)一贴通（资料大全） [精品] 【资料整理】自考高等数学(工本)一贴通（资料大全） [精品] 【资料整理】自考自考网络操作系统一贴通（资料大全） [精品] 【资料整理】自考数据结构一贴通（资料大全） [精品] 【资料整理】自考数据库系统原理一贴通（资料大全） [精品] 【资料整理】自考英语二一贴通（资料大全） [精品] 【资料整理】自考互联网及其应用一贴通（资料大全） [精品] 【资料整理】自考计算机网络管理一贴通（资料大全） [精品]【资料整理】自考计算机网络安全一贴通（资料大全） [精品] -------------------------------------------------- 最后预祝所有的朋友: 自考快乐 天天有份好心情！！！-------------------自考乐园俱乐部 ===========================================================关于自考，你还有什么疑惑，欢迎在百度上给我留言，我会尽力帮助你的...如果你要加入自考乐园俱乐部，也欢迎给我留言，我会给你发邀请链接...==============================================================百度贴吧：自考乐园俱乐部 参考资料：百度贴吧：自考乐园俱乐部 楼上的太强悍了...我不得不佩服...本来我也想回答一下...这下我只好无语了...真不知道，自考乐园办的这么好......数据结构自考试卷真题答案
数据结构自考本科试题及答案
数据结构自考试卷真题和答案