下载文档原格式
全国2011年1月自学考试数据结构导论试题和答案课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为( )A.O(1)B.O(n)C.O(log2n)D.O(n)2.树形结构中，度为0的结点称为( )A.树根B.叶子C.路径D.二叉树3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>，<V1,V3>，<V1,V4>，<V2,V5>，<V3,V5>,<V3,V6>，<V4,V6>，<V5,V7>,，<V6,V7>}，则图G的拓扑序列是( )A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V74.有关图中路径的定义，表述正确的是( )A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5.串的长度是指( )A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数6.组成数据的基本单位是( )A.数据项B.数据类型C.数据元素D.数据变量7.程序段i=n；x=0；do{x=x+5*i；i--；}while （i>0）；的时间复杂度为( )A.O（1）B.O（n）C.O（n2）D.O(n3)8.与串的逻辑结构不同的．．．数据结构是( )A.线性表B.栈C.队列D.树9.二叉树的第i（i≥1）层上所拥有的结点个数最多为( )A.2iB.2iC.2i-1D.2i-110.设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( )全国2011年1月自学考试数据结构导论试题和答案 1A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.p->next=p11.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )A.堆排序B.冒泡排序C.直接插入排序D.快速排序12.设字符串S1=″ABCDEFG″，S2=″PQRST″，则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后S的结果为( )A.″BCQR″B.″BCDEF″C.″BCDEFG″D.″BCDEFEF″13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则使其平衡的调整方法为( )A.LL型B.LR型C.RL型D.RR型14.如果结点A有3个兄弟结点，而且B为A的双亲，则B的度为( )A.1B.3C.4D.515.数据表A中每个元素距其最终位置较近，则最省时间的排序算法是( )A.堆排序B.插入排序C.直接选择排序D.快速排序二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。
福建工程学院课程设计课程：算法与数据结构题目：哈希表专业：网络工程班级：xxxxxx班座号：xxxxxxxxxxxx姓名：xxxxxxx2011年12 月31 日实验题目：哈希表一、要解决的问题针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。
以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。
基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。
完成按姓名查询的操作。
运行的环境：Microsoft Visual C++ 6.0二、算法基本思想描述设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。
建立哈希表并且将其显示出来。
通过要查找的关键字用哈希函数计算出相应的地址来查找人名。
通过循环语句调用数组中保存的数据来显示哈希表。
三、设计1、数据结构的设计和说明（1）结构体的定义typedef struct //记录{NA name;NA xuehao;NA tel;}Record;录入信息结构体的定义，包含姓名，学号，电话号码。
typedef struct //哈希表{Record *elem[HASHSIZE]; //数据元素存储基址int count; //当前数据元素个数int size; //当前容量}HashTable;哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。
2、关键算法的设计（1）姓名的折叠处理long fold(NA s) //人名的折叠处理{char *p;long sum=0;NA ss;strcpy(ss,s); //复制字符串，不改变原字符串的大小写strupr(ss); //将字符串ss转换为大写形式p=ss;while(*p!='\0')sum+=*p++;printf("\nsum====================%d",sum);return sum;}（2）建立哈希表1、用除留余数法构建哈希函数2、用线性探测再散列法处理冲突int Hash1(NA str) //哈希函数{long n;int m;n=fold(str); //先将用户名进行折叠处理m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数return m; //并返回模值}Status collision(int p,int c) //冲突处理函数，采用二次探测再散列法解决冲突{int i,q;i=c/2+1;while(i<HASHSIZE){if(c%2==0){c++;q=(p+i*i)%HASHSIZE;if(q>=0) return q;else i=c/2+1;}else{q=(p-i*i)%HASHSIZE;c++;if(q>=0) return q;else i=c/2+1;}}return UNSUCCESS;}void benGetTime();}else printf("\n此人不存在，查找不成功!\n");benGetTime();}（4）显示哈希表void ShowInformation(Record* a) //显示输入的用户信息{int i;system("cls");for( i=0;i<NUM_BER;i++)printf("\n第%d个用户信息:\n 姓名：%s\n 学号：%s\n 电话号码：%s\n",i+1,a[i].name,a[i].xuehao,a[i].tel);}（5）主函数的设计void main(int argc, char* argv[]){Record a[MAXSIZE];int c,flag=1,i=0;HashTable *H;H=(HashTable*)malloc(LEN);for(i=0;i<HASHSIZE;i++){H->elem[i]=NULL;H->size=HASHSIZE;H->count=0;}while (1){ int num;printf("\n ");printf("\n 欢迎使用同学通讯录录入查找系统");printf("\n 哈希表的设计与实现");printf("\n 【1】. 添加用户信息");printf("\n 【2】. 读取所有用户信息");printf("\n 【3】. 以姓名建立哈希表(再哈希法解决冲突) ");printf("\n 【4】. 以电话号码建立哈希表(再哈希法解决冲突) ");printf("\n 【5】. 查找并显示给定用户名的记录");printf("\n 【6】. 查找并显示给定电话号码的记录");printf("\n 【7】. 清屏");printf("\n 【8】. 保存");printf("\n 【9】. 退出程序");printf("\n 温馨提示：");printf("\n Ⅰ.进行5操作前请先输出3 ");printf("\n Ⅱ.进行6操作前请先输出4 ");printf("\n");printf("请输入一个任务选项>>>");printf("\n");scanf("%d",&num);switch(num){case 1:getin(a);break;case 2:ShowInformation(a);break;case 3:CreateHash1(H,a); /* 以姓名建立哈希表*/break;case 4:CreateHash2(H,a); /* 以电话号码建立哈希表*/break;case 5:c=0;SearchHash1(H,c);break;case 6:c=0;SearchHash2(H,c);break;case 7:Cls(a);break;case 8:Save();break;case 9:return 0;break;default:printf("你输错了，请重新输入!");printf("\n");}}system("pause");return 0;3、模块结构图及各模块的功能：四、源程序清单：#include<stdio.h>#include<stdlib.h>#include<string.h>#include <windows.h>#define MAXSIZE 20 #define MAX_SIZE 20 #define HASHSIZE 53 #define SUCCESS 1#define UNSUCCESS -1#define LEN sizeof(HashTable)typedef int Status;typedef char NA[MAX_SIZE];typedef struct {NA name;NA xuehao;NA tel;}Record;typedef struct {Record *elem[HASHSIZE]; int count; int size; }HashTable;Status eq(NA x,NA y) {if(strcmp(x,y)==0)return SUCCESS;else return UNSUCCESS;}Status NUM_BER;void getin(Record* a) {int i;system("cls");printf("输入要添加的个数：\n");scanf("%d",&NUM_BER);for(i=0;i<NUM_BER;i++){printf("请输入第%d个记录的姓名:\n",i+1);scanf("%s",a[i].name);printf("请输入%d个记录的学号:\n",i+1);scanf("%s",a[i].xuehao);printf("请输入第%d个记录的电话号码:\n",i+1);scanf("%s",a[i].tel);}}void ShowInformation(Record* a){int i;system("cls");for( i=0;i<NUM_BER;i++)printf("\n第%d个用户信息:\n 姓名：%s\n 学号：%s\n 电话号码：%s\n",i+1,a[i].name,a[i].xuehao,a[i].tel);}void Cls(Record* a){printf("*");system("cls");}long fold(NA s){char *p;long sum=0;NA ss;strcpy(ss,s);strupr(ss);p=ss;while(*p!='\0')sum+=*p++;printf("\nsum====================%d",sum);return sum;}int Hash1(NA str){int m;n=fold(str);m=n%HASHSIZE;return m;}int Hash2(NA str){long n;int m;n = atoi(str);m=n%HASHSIZE;return m;}Status collision(int p,int c){int i,q;i=c/2+1;while(i<HASHSIZE){if(c%2==0){c++;q=(p+i*i)%HASHSIZE;if(q>=0) return q;else i=c/2+1;}else{q=(p-i*i)%HASHSIZE;c++;if(q>=0) return q;else i=c/2+1;}}return UNSUCCESS;}void benGetTime();void CreateHash1(HashTable* H,Record* a){ int i,p=-1,c,pp;system("cls"); benGetTime();for(i=0;i<NUM_BER;i++){p=Hash1(a[i].name);pp=p;while(H->elem[pp]!=NULL) {pp=collision(p,c);if(pp<0){printf("第%d记录无法解决冲突",i+1);continue;}}H->elem[pp]=&(a[i]);H->count++;printf("第%d个记录冲突次数为%d。
1、有向图采用邻接矩阵存储，某一行中非零元素的个数等于 A．对应顶点v 的度 B．对应顶点v的出度 C．对应顶点v的入度 D．依附于对应顶点v的边数2、在一个长度为n（n>1）的单链表上，设有头和尾两个指针，执行 B 操作与链表的长度有关。
A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素C．在单链表第一个元素前插入一个新元素 D．在单链表最后一个元素后插入一个新元素3、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。
A．单链表 B．静态链表 C．线性链表 D．顺序存储结构4、在二维数组a[9][10]中：每个数组元素占用3个存储空间，从首地址SA开始按行优先连续存放，则元素a[8][5]的起始地址是 A．SA+141 B．SA+144 C．SA+222 D．SA+255 5、链表不具备的特点是 A 。
A．可随机访问任一结点 B．插入删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与其长度成正比 6、栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是 A．顺序栈需要判定栈空，链栈也需要判定 B．顺序栈需要判定栈空，而链栈不需要判定 C．顺序栈不需要判定栈空，而链栈需要判定 D．顺序栈不需要判定栈空，链栈也不需要判定 7、向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( 。
A．O(n B．O(1C．O(n2 D．O(10g2n 8、深度为k的完全二叉树所含叶结点的个数最多为（ B）。
A）2k B） 2k-1 C）k D） 2k 9、若进栈序列为1，2，3，4，则不可能得到的出栈序列是（ C ）。
A）3，2，1，4 B）3，2，4，1 C）4，2，3，1 D）2，3，4，1 10、已知关键字序列为{66，82，25，51，98，108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为 A．{25，51，66，82，98，108} B．{25，51，66，98，82，108} C．{51，25，66，108，98，82} D．{51，25，66，82，98，108} 11、已知关键字序列为{66，82，25，51，98，108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为 A．{25，51，66，82，98，108} B．{25，51，66，98，82，108} C．{51，25，66，108，98，82} D．{51，25，66，82，98，108} 12、栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是 A．顺序栈需要判定栈空，链栈也需要判定 B．顺序栈需要判定栈空，而链栈不需要判定 C．顺序栈不需要判定栈空，而链栈需要判定 D．顺序栈不需要判定栈空，链栈也不需要判定 13、如果最常用的操作是取第i个结点及其前驱，则采用 D 存储方式最节省时间。
1、下列各种数据结构中属于线性结构的有（ A ）。
A）栈 B) 二叉树C) 广义表 D) 图2、数据结构研究的内容是（ D ）。
A）数据的逻辑结构 B）数据的存储结构C）建立在相应逻辑结构和存储结构上的算法 D）包括以上三个方面3、线性表的链接实现有利于（ A ）运算。
A）插入 B）读元素C）查找 D）定位4、二叉树第i(i≥1)层上至多有（ C ）结点。
A）2i B）2i C）2i-1 D）2i-15、数据结构研究的内容是（ D ）。
A）数据的逻辑结构 B）数据的存储结构C）建立在相应逻辑结构和存储结构上的算法 D）包括以上三个方面6、栈进行插入和删除操作的特点是（ A ）。
A）LIFO B）FIFOC）FCFS D）HPF7、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。
A）4 B）5C）6 D）78、已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。
A) Head(Head(Tail(Tail(L))))B) Tail(Head(Head(Tail(L))))C) Head(Tail(Head(Tail(L))))D)Head(Tail(Head(Tail(Tail(L)))))9、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。
A）3 B）4 C）5 D）110、下面关于线性表的叙述中，错误的是哪一个？（ D ）A）线性表采用顺序存储，必须占用一片连续的存储单元。
B）线性表采用链接存储，便于插入和删除操作。
C）线性表采用链接存储，不必占用一片连续的存储单元。
D）线性表采用顺序存储，便于进行插入和删除操作。
11、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。
A） (G) B） (D) C） C D） D12、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。
长治学院课程设计报告课程名称：数据结构课程设计设计题目：克鲁斯卡尔算法求最小生成树系别：计算机系专业：组别：学生姓名：学号:起止日期: 2011年6月29日~2011年7月6日指导教师: 马强目录1. 需求分析 (2)1.1 设计题目 (2)1.2 设计任务及要求 (2)1.3课程设计思想 (2)1.4 程序运行流程: (2)1.5软硬件运行环境及开发工具 (2)2.概要设计 (2)2.1流程图 (2)2.2抽象数据类型MFSet的定义 (3)2.3主程序 (3)2.4抽象数据类型图的定义 (4)2.5抽象数据类型树的定义 (6)3. 详细设计 (8)3.1程序 (8)4.调试与操作说明 (11)4.1测试结果 (11)4.2调试分析 (12)5.课程设计总结与体会 (12)5.1总结 (12)5.2体会 (12)6. 致谢 (13)7. 参考文献 (13)8.附录 (14)1.需求分析1.1 设计题目：最小生成树1.2 设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。
1.3 课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。
最短边策略从TE={}开始，每一次贪心选择都是在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。
)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。
1.4程序运行流程:1)提示输入顶点数目；2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树；3)输出最小生成树并且退出；1.5 软硬件运行环境及开发工具：VC2.概要设计2.1流程图开始定义数据类型定义图定位定义图中的顶点数和边数Kruskal算法主程序图1流程图2.2抽象数据类型MFSet的定义：ADT MFSet {数据对象：若设S是MFSet型的集合，则它由n(n>0)个子集Si（i = 1,2...,n）构成，每个子集的成员代表在这个子集中的城市。
全国2011年1月高等教育自学考试数据结构试题（课程代码：02331）一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.下列选项中与数据存储结构无关的术语是（）A.顺序表B.链表C.链队列D.栈2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（）A.n-1B.nC.2n-1D.2n3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（）A.rear=(rear-1)%m;B.front=(front+1)%m;C.front=(front-1)%m;D.rear=(rear+1)%m;4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（）A.堆栈B.多维数组C.队列D.线性表5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（）A.求子串B.串联接C.串匹配D.求串长6.对于广义表A，若head(A)等于tail(A)，则表A为（）A.( )B.(( ))C.(( ),( ))D.(( ),( ),( ))7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（）A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树C.高度为n的二叉树D.存在度为2的结点的二叉树8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（）A.4B.5C.7D.89.下列叙述中错误的是（）A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次B.图的遍历可以采用深度优先遍历和广度优先遍历C.图的广度优先遍历只适用于无向图D.图的深度优先遍历是一个递归过程10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={<V1，V2>，<V1，V3>，<V2，V3>，<V2，V4>，<V3，V4>}，图G的拓扑序列是（）A.V1,V2,V3,V4B.V1,V3,V2,V4C.V1,V3,V4,V2D.V1,V2,V4,V311.平均时间复杂度为O(n log n)的稳定排序算法是（）A.快速排序B.堆排序C.归并排序D.冒泡排序12.已知关键字序列为(51，22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的关键字序列是（）A.(18,22,30,46,51,68,75,83)B.(30,18,22,46,51,75,83,68)C.(46,30,22,18,51,75,68,83)D.(30,22,18,46,51,75,68,83)13.某索引顺序表共有元素395个，平均分成5块。
算法与数据结构考试试卷试题库试题卷计算机科学与技术系算法与数据结构课程建设小组编写2011-11-21 第3稿一、选择题1.在数据结构教材中,从存储结构上可以把数据结构分成（）。
A.顺序存储和链式存储B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.动态结构和静态结构2.线性表是n个（）的有限序列。
A.字符B.数据元素C.数据项D.信息项3.有六个元素按6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列（）。
A. 5 4 3 6 1 2B. 4 5 3 1 2 6C.3 4 6 5 2 1D.2 3 4 1 5 64.不带头结点的单链表存储的队列中，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5.为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片内存空间时，应将两个栈的（）分别设在这片内存空间的两端，只有当两个栈的栈顶在栈空间的某个位置相遇时，才产生上溢。
A.长度B.深度C.栈底D.栈顶6．（）是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。
A.数据对象B.数据项C.数据类型D.数据集合7．从逻辑结构上看，下列结构（）不属于基本逻辑结构中的线性结构。
A.字符串B.数组C.队列D.图8．一棵具有n个结点的完全二叉树的树高度（深度）是（）A .log2n+1 B.log2n +1C.log2nD.log2n-19.二叉树的第i层上最多含有结点数为（）。
A.2iB.2i-1-1C.2i-1D.2i-110. 由3 个结点可以构造出多少种不同的二叉树？（）A.2B.3C.4D.511. 在长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时，需要向后移动（）个元素。
A.n－iB.n－i+1C.n－i－1D.i12．引入二叉线索树的目的是（）A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果惟一13. 有n个叶子的哈夫曼树的结点总数为（）A.不确定B.2nC.2n+1D.2n-114．利用二叉链表存储树时，根结点的右指针是（）A.指向最左孩子B.指向最右孩子C.空D.非空15．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )A.1和5B.2和4C.4和2D.5和116. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。
一、选择题1. 评价一个算法时间性能的主要标准是(D )。
A、算法易于调试B、算法易于理解C、算法的稳定性和正确性D、算法的时间复杂度2. 计算机算法具备有输入、输出、（B ）等五个特性。
A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性3. 带头结点的单链表head为空的判定条件是（B ）。
A、head==NULLB、head->next==NULLC、head->next==headD、head！=NULL4. 以下关于线性表的说法不正确的是( C)。
A、线性表中的数据元素可以是数字、字符、记录等不同类型。
B、线性表中包含的数据元素个数不是任意的。
C、线性表中的每个结点都有且只有一个直接前趋和直接后继。
D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。
5. 在顺序表中，只要知道(D )，就可在相同时间内求出任一结点的存储地址。
A、基地址B、结点大小C、向量大小D、基地址和结点大小6. ( C)运算中，使用顺序表比链表好。
A、插入B、删除C、根据序号查找D、根据元素值查找7. 一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动（B）个元素。
A、n-iB、n-i+1C、n-i-1D、i8. (D )适合作为经常在首尾两端操作线性表的存储结构。
A、顺序表B、单链表C、循环链表D、双向链表9. 栈和队列的共同点是（C）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10. 一个队列的入列序列是1 2 3 4，则队列的输出序列是(B )。
A、4 3 2 1B、1 2 3 4C、1 4 3 2D、3 2 4 111. 队列与一般的线性表的区别在于(D )。
A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同12. “假上溢”现象会出现在(C )中。
A、循环队列B、队列C、链队列D、顺序队列二、填空题1．数据的逻辑结构被分为集合、线性结构、树形结构和图结构。
2011级数据结构试卷A一、单选题：（每题1.5分，共30分）1、以下函数增长率最大的是A、(3/2)nB、n C 、log2n D、n!2、设某算法与问题规模的函数关系为f(n)=5000n3.5+nlogn，则使用大O表示法，其时间复杂度可表示为：A、O(n)B、O(5000)C、O(nlogn)D、O(n3.5)3、在具有n个单元的顺序储存的循环队列中，假定front和rear 分别为队头指针和队尾指针，则判断队满的条件为__( )A、rear%n=frontB、(front+1)%n=rearC、rear%n-1=frontD、(rear+1)%n=front4、下列陈述中正确的是（）A、二叉树是度为2的有序树B、二叉树中结点只有一个孩子时无左右之分C、二叉树中必有度为2的结点D、二叉树中最多只有两棵子树，并且有左右之分5、一个顺序表第一个元素存储的地址是100，每个元素的长度为2，则第五个元素的地址是：( )A、110B、108C、100D、1206、在单向循环链表中，若头指针为first，那么p所指结点为尾结点的条件是（）A、p=NULLB、p.next=NULLC、p=firstD、p.next=first7、若要在O（1）的时间复杂度上实现两个单向循环链表头尾相接，则应对两个单向循环链表各设置一个指针，分别指向（ b ）A、各自的头结点B、各自的尾结点C、各自的第一个元素结点D、一个表的头结点，另一个表的尾结点8、与线性表的链接存储不相符合的特性是（）A、便于插入、删除操作B、存贮空间动态分配C、需要连续的存贮空间D、只能顺序查找9、在待排序的元素序列基本有序的前提下，以下排序方法中效率最高的是( )A、起泡排序B、堆排序C、快速排序D、归并排序10、线性表L =（a1, a2, ．．．, an）,下列说法正确的是：__________A、每个元素都有一个直接前驱和直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继11、若已有一个栈，输入序列为A，B，C，D，E，那么下面哪种出栈序列不可能得到？（）A、ABCDEB、EDCBAC、BAEDCD、ECDBA12、以下说法错误的是( )A、一般在哈夫曼树中，权值越大的叶子离根结点越近B、哈夫曼树中没有度数为1的分支结点C、若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点D、若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树13、设二叉树的根为第1层，则高度为k的二叉树最大结点数有（）A、2kB、2k－1C、2k-1D、2k-1－114、在以下排序方法中，关键字比较的次数与记录的初始排列次序无关系的是（）A、希尔排序B、起泡排序C、直接插入排序D、归并排序15、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（）A、4B、5C、6D、716、按照二叉树的定义，具有3个结点的二叉树有( ) 种形态A、3B、4C、5D、617、一棵二叉树的顺序存储结构如下，空值表示不存在该结点：2 3 7 12 10 11 17 5 30 21则值为7的结点的右孩子的值为____________。
数据结构课程设计题目以下7个题目任选其一。
1．排序算法比较利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并且（1）统计每一种排序上机所花费的时间。
（2）统计在完全正序，完全逆序情况下记录的比较次数和移动次数。
（3）比较的指标为关键字的比较次数和记录的移动次数(一次记录交换计为3次移动)。
（4）对结果作简单分析，包括对各组数据得出结果波动大小的解释。
2．图的深度遍历对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索遍历。
画出搜索顺序示意图。
3．图的广度遍历对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。
画出搜索顺序示意图。
4．二叉树的遍历对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。
画出搜索顺序示意图。
5．链表操作利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。
画出搜索顺序示意图。
6．一元稀疏多项式简单计数器（1）输入并建立多项式（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。
序列按指数降序排列。
（3）多项式a和b相加，建立多项式a+b，输出相加的多项式。
（4）多项式a和b相减，建立多项式a-b，输出相减的多项式。
用带头结点的单链表存储多项式。
测试数据：（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)7．实现两个链表的合并基本功能要求：（1）建立两个链表A和B，链表元素个数分别为m和n个。
《数据结构》课程设计 一、题目的选择方法 根据学号进行对应题目的选择，即学号的后2位除以17取余数，所得余数即为该同学所选题号。
二、《数据结构》课程设计可供选择的题目 1、 Huffman编码的应用 创建一个文本文件，通过统计该文件中各字符出现的频率，对各字符进行Huffman编码，（1）能够实现将该文件转换成Huffman编码文件存储（压缩），（2）能够实现将Huffman编码文件还原成原文件（解压）。
2、链表的应用 以有序的单链表结构来描述超市家电部的库存模型。当有提货或进货时需要对该链表及时进行维护。每个工作日结束之后，将该链表中的数据以文件形式保存，每日开始营业之前，需将以文件形式保存的数据恢复成链表结构的有序表。链表结点的数据域包括家电名称、品牌、单价和数量，以单价的升序体现链表的有序性。程序功能包括：初始化、创建表、插入、删除、更新数据，查询及链表数据与文件之间的转换等。
3、Hash表的应用 扫描一个C语言源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频率。
4、图的应用 N(N>10)个居民之间需要铺设煤气管道。假设任意两个居民之间都可以铺设煤气管道，但代价不同。事先将任意两个居民之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民之间铺设煤气管道所需代价最少。 5、模式匹配算法的应用 利用字符串匹配的KMP算法，实现对文本文件的查找与替换功能。 6、Joseph环 约瑟夫环（Joseph）问题的一种描述是：编号为1、2、3„„n的n个人按照顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按照顺时针的方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 [基本要求] 利用顺序表、单向循环链表两种存储结构模拟此过程，按照出列的顺序依次输出每个人的编号。 ［测试数据］ m的初值为20，n=7,7个人的密码依次为：3、1、7、2、4、8、4，首先m值为6（正确的出列顺序应为6、1、4、7、2、3、5）。 ［实现提示］ 程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。可设n≤30。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。 7、长整数四则运算 ［问题描述］ 设计一个实现任意长的整数进行加法运算的演示程序 [基本要求] 利用双向循环链表实现长整数的存储，每个节点包含一个整型变量。任何整型变量的范围是-（215－1）～215－1，输入输出形式：按照中国对于长整数的表示习惯，每四位一组，组间用逗号分开。 [测试数据] （1）0；0；应输入“0” （2）-2345,6789;-7654,3211;应输出”-1,0000,0000” （3）1,0001,0001;-1,0001,0001;应输出0。 ［实现提示］ 每个结点中可以存放的最大整数为215－1＝32767，才能保证两数相加不会溢出。但若这样存放，即相当于按32767进制数存放，在十进制数与32767进制数之间的转换十分不便。故可以在每个节点中仅存放十进制数的4位，即不超过9999的非负整数，整个链表表示为万进制数。
可以利用头节点的数据域的符号代表长整数的符号。相加过程中不要破坏两个操作数链表。不能给长整数位数规定上限。 8、栈的应用一 表达式计算是实现程序设计语言的基本问题之一。也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法或转换成后缀表达式方法对算术表达式进行求值的过程。 [基本要求] 以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用算符优先关系，或中缀表达式向后缀表达式转换的方法，实现对算术四则混合运算表达式的求值，并仿照教科书和课件中的例子演示求值中运算符栈、运算数栈、输入字符和主要操作变化的过程。 [测试数据］ 3＊（7－2） 8；1＋2＋3＋4；88－1＊5；1024／4＊8；（6＋2＊（3＋6＊（6＋6）））
9、二分法查找的应用 分块查找又称为索引顺序查找，是顺序查找的一种改进方法。除了表自身之外，尚需建立一个“索引表”，为每一个子表建立一个索引项，其中包括两项内容，关键字（子表内的最大关键字）项和指针项（子表中第一个记录在表中的位置）。索引表按关键字排序，子表分块有序，查找时先确定待查记录所在的块，然后在块内查找。由于索引项是按照关键字排序的，所以在索引表中的查找可以采用二分查找方法。 [基本要求] （1） 将学生按照班级进行分类，同一班级的学生记录在一个子表中。 （2） 索引表中存放班级的名称，并按照名称进行排序。 （3） 一个班级的学生记录可以不按照顺序存放。 [测试数据] 自行设置。 [实现提示] (1) 可假设要存储的班级数最多为20个，一个班级最多有30个学生。 (2) 所有班级的学生记录都存放在同一个连续的存储空间中。每个班级学生记录存储的起始位置固定。 (3) 索引表另行建立，用于存储每个班级的学生在子表中存储的起始位置和人数。
10、哈希表的设计 针对你所在的集体（比如你所在的班级）中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表的程序。 [基本要求] 假设人名为中国人姓名的汉语拼音形式，待填入的哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数方法构造，用伪随机探测再散列处理冲突。 [测试数据] 取你周围熟悉的30个人的姓名。 [实现提示] 如果随机函数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符，最长的人名如：庄双双（Zhuang Shuangshuang）。字符的取码方法可直接利用C语言中的toascii函数，并可对过长的人名先作折叠处理。
11、二叉排序树的应用 使用二叉排序树进行表的建立和查找算法。 [基本要求] 将自己的联系人按照联系人的电话号码关键字建立二叉排序树，并实现在建立的二叉排序树上进行查找操作。联系人的信息可以有：姓名、性别、出生年月日、家庭住址和另一个联系电话等信息。 ［测试数据］ 自行设定。 12、多关键字排序的应用 多关键字的排序有一定的实用范围。例如：在即行高考分数的处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此上需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的顺序。 [基本要求] （1）假设待排序的记录不超过10，000，表中记录的关键字不超过5个，各个关键字的范围均为0至100。按照用户给定的进行排序的关键字的优先关系，输出排序的结果。 （2）约定按照LSD（最低位优先法，Least Significant Digit first，简称LSD法。）进行多关键字的排序。在对各个关键字进行排序时采用两种策略：其一是利用稳定的内部排序算法，其二是利用“分配”和“收集”的方法。并综合比较这两种策略。 ［测试数据］ 由随机数产生器产生。 [实现提示] 用5～8组数据比较不同排序策略所需要的时间。 由于是按LSD方法进行排序，则对于每一个关键字均可进行整个序列的排序，但在利用通常的内部排序算法进行排序时，必须选用稳定的排序算法。借助“分配”和“收集”策略进行的排序，如同一趟“基数排序”，由于关键字的取值范围为0至100，则分配时使得到101个链表。 13、排序算法的比较 在教科书中，各种排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字比较次数和关键字移动次数，以取得直观感受。 [基本要求] （1） 对以下四种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序和归并排序。 （2） 待排序的表长不小于100，其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据做比较；比较的指标有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。 （3） 最后要对结果做出简单分析，包括对各组数据得出结果波动大小的解释。 [测试数据] 由随机数产生器生成。 [实现提示] 主要的工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如：正序、逆序和不同程度的乱序。注意采用分块调试的方法。
14、重言式判别问题 一个逻辑表达式如果对于其变元的任一种取值均为真，则成为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式，然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。， [基本要求] （1） 逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“｜”、“＆”和“～”，分别表示或、与和非，运算优先程度递增，但可有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。 （2） 若是重言式或矛盾式，可以只显示“True Forever”或“False Forever”，否则显示“Satisfactible”以及变量名序列，与用户交互。若用户对表达式变元取定一组值，程序就求出并显示逻辑表达式的值。 [测试数据] （1）（A｜～A）＆（B|~B） （2）（A&～A）＆C （3）A|B|C|D|E｜～A [实现提示] (1) 识别逻辑表达式的符号形式并建立二叉树可以有两种策略：自底向上的算符优先法和自顶向下分割，先序遍历建立二叉树的方法。 (2) 可设表达式中逻辑变量数不超过20。真值的产生可以通过在一维数组上维护一个“软计数器”实现，用递归算法实现更简单。
