数据结构期末考试试题和标准答案及评分标准(共11页).doc

精选优质文档-倾情为你奉上数据结构试题（A卷）（考试时间： 90分钟） 一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（ ）是组成数据的基本单位，是一个数据整体中相对独立的单元。A数据 B.数据元素C.数据对象D.数据结构2.算法计算量的大小称为算法的（ ）。A.效率     B.复杂度 C.数据元素之间的关系    D.数据的存储方法3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（ ）方式最节省时间。A.链式存储 B. 索引存储 C.顺序存储 D.散列存储4.下述哪一条是顺序存储结构的优点？（ ）A.存储密度大  B.插入运算方便  C.删除运算方便  D.可方便地用于各种逻辑结构的存储表示5.在一个单链表中，若删除p所指结点的后续结点，则执行（ ）。A.p->next=p->next->next B.p->next=p->nextC.p=p->next;p->next=p->next->next D.p=p->next->next 6.带头结点的单链表head为空的判定条件是（ ）。A.head=NULL B.head->next=NULLC.head->next=headD.head!=NULL7.非空的循环单链表head的尾结点(由p所指向)满足（ ）。A.p->head=NULLB.p=NULLC.p->next=head D.p=head8.下面关于线性表的叙述中，错误的是哪一个？（ ）A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链式存储，不必占用一片连续的存储单元。D.线性表采用链式存储，便于插入和删除操作。9.队列操作的原则是（ ）。A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（ ）。 A.栈首 B.栈尾 C.栈顶 D.栈底11假设以数组An存放循环队列的元素，其首尾指针分别为front和rear，则当前队列中的元素个数为（ ）。A（rear-front+n）%n B. rear-front+1C. (front-rear+n)%n D.(rear-front)%n12.最大容量为n的循环队列，队尾指针是rear，队首指针是front，则队空的判断条件是（ ）。A.（rear+1）%n=front B.rear=frontC.rear+1=front D.(rear-1)%n=front13. 将一个十进制的数转换成二进制的数，可以使用以下一种称为（ ）的数据结构。A. 图 B. 树 C. 广义表 D. 栈14. 把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。A. 有2种 B. 有3种 C. 有4种 D. 唯一的15.一棵左右子树均不空的二叉树在先序线索化后，其中空链域的个数是（ ）。A. 3 B. 2 C. 0 D. 不确定二、填空题（本大题共10个空，每空2分，共计20分）1数据结构是研究程序设计中计算机操作的 以及它们之间的关系和运算的一门学科。2在一个单链表中，已知指针q所指结点是指针p 所指结点的前驱结点，若在q和p之间插入结点s，则应执行两条语句：_ _ ， 。3字符串采用结点大小为2的链表作为其存储结构，是指链表的每个链结点的 域中只存放了2个字符。4广义表（a,b,c,d）的表尾是 。5一棵深度为k的二叉树，最多有 个结点。6已知有向图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的拓扑序列是_ _ _。7. 有n个顶点的连通图至少有 条边。8. 图的存储常采用 和 两种方法。三、判断题（本大题共10小题，每题1分，共10分）（请在每小题后面的括号里写出答案，如果正确，请写“”，如果错误，请写“×”）1.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ）2线性表就是顺序存储的表。（ ）3.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。（ ）4线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构。（ ）5.串的长度是指串中所含不同字符的个数。（ ）6.对稀疏矩阵进行压缩存储的目的是节省存储空间。（ ）7.二叉树是非线性数据结构，所以它不能采用顺序存储结构存储。（ ）8.任意一棵二叉树中至少有一个结点的度为2。（ ）9.对线性表进行二分查找时，要求线性必须以顺序方式存储，且结点按关键字有序排序。（ ）10.采用线性探测法解决冲突问题，所产生的一系列后继散列地址必须大于等于原散列地址。（ ）四、应用题（本小题共5小题，每小题6分，共30分）1.简述以下算法的功能（假设栈和队列的元素类型均为int）(6分)void fun1(Queue &Q)Stack S;int x;Initstack(S);While(!QueueEmpty(Q) DeQueue(Q,x); Push(S,x); While(!StackEmpty(S) Pop(S,x); EnQueue(Q,x); 2.请将如图4.1所示的一棵树转换成一棵二叉树。（6分）图4.1 一棵树3.给定叶结点(a,b,c,d,e,f,g)，权值分别为23,12,15,7,17,2,8，画出对应的哈夫曼树，并写出各叶结点的哈夫曼编码。（6分）4.（6分）已知图G的邻接表如图4.2所示，则：从顶点v1出发的深度优先搜索序列为_ _ _。从顶点v1出发的广度优先搜索序列为_ _ _。图4.2 图G的邻接表âââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââ密封线密封线5.求构造图4.3所示无向网的最小生成树（6分）图4.3 无向网五、算法设计题（本大题共1小题，每小题10分，共10分）1.已知查找表的数据元素类型如下：Typedef struct Rectypeint num;char name8;Rectype; 假设查找表中有n个记录，并且是按num降序顺序存储Typedef Rectype Sqlist100;要求：（1）写出对给定值K进行二分查找的算法和main函数。（2）二分查找算法的函数头部为“int binsearch(Sqlist R,int n,int K) “（3）在main函数中建立该查找表、调用二分查找算法，并输出查找结果。数据结构试题（B卷）（考试时间：90 分钟） 一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1在数据结构中，数据的（ ）结构是独立于计算机的。A.逻辑 B.存储 C.散列 D.索引2下列程序段的时间复杂度为（ ）。for(i=0;i<n;i+) x=x-2;A.O（2n）    B.O（n） C. O（1） D. O（n2）3. 链式存储结构表示的线性表也称为（ ）。 A.链表 B.顺序表 C.双链表 D.物理表4.不带头结点的单链表（头指针为head）为空的判定条件是（ ）。 Ahead=NULL Bhead->next=head Chead->next=NULL Dhead!=NULL5线性表若采用顺序结构时，要求内存中可用存储单元的地址（ ）。A一定是不连续的 B部分地址是连续的C一定是连续的 D连续不连续都可以6. 对于单链表，在两个结点之间插入一新结点需要修改的指针共（ ）个。A.0B.1 C.2 D.47.若线性表中有n个元素，算法（ ）在单链表上实现要比在顺序表上实现效率更高。A.删除所有值为x的元素 B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素 D.交换其中某两个元素的值8.对于顺序表，访问结点和增加、删除结点的时间复杂度分别为（ ）。A.O(n)O(n) B. O(1)O(n) C. O(n) O(1)D. O(1) O(1)9.队列的删除操作是在（ ）进行。A队首 B队尾 C队首前一单元 D队尾后一单元10.下列关于栈的叙述中，正确的是（ ）。A栈底元素一定是最后入栈的元素 B栈操作遵循先进后出的原则C栈顶元素一定是最先入栈的元素 D以上三种说法都不对11.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S ,一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少是（ ）个。A.3 B. 4 C.5 D.612.假设为循环队列分配的向量空间为Q20,若队列的长度和队头指针值分别为13和17，则当前尾指针的值为_。A.10 B.11 C.12  D.1313.银行业务叫号系统采用了 数据结构。A栈 B广义表 C队列D图14.按照二叉树的定义，具有3个结点的不同形状的二叉树有_种。A.3B.4 C.5 D.615. n个结点的线索二叉树上含有的线索数为_。A.0B.n-1 C.n+1 D.2n二、填空题（本大题共10个空，每空2分，共20分）1数据结构包含三个方面的内容，即数据的逻辑结构 、数据的 结构和对数据所施加的操作。2已知指针q值为NULL、指针p指向单链表L中的某结点，则删除其后继结点（要求由指针q指向）的语句是 ， ，free(q)。3设广义表L=（a,( )） ,则Head(L)= 。4当且仅当两个串的 相等并且各个对应位置上的字符都相等时，称这两个串相等。5.二叉树的第4层结点数最多为 个。6除了利用求关键路径的方法，还可以利用 方法判断出一个有向图是否有环（回路）。7图的遍历主要有 和 两种方法。8. 具有4个顶点的无向完全图有 条边。三、判断题（本大题共10小题，每题1分，共10分）（请在每小题后面的括号里写出答案，如果正确，请写“”，如果错误，请写“×”）1.对于一个线性表，采用顺序存储方式进行插入和删除结点时效率太低，采用链式存储方式更好。（ ）2.所谓静态链表就是一直不发生变化的链表。（ ）3.在顺序表中，最后一个元素有一个后继。（ ）4.线性表就是链式存储的表。（ ）5.串是一种特殊的线性表，其特殊性体现在数据元素可以是多个字符。（ ）6.对稀疏矩阵进行压缩存储的目的是便于输入和输出。（ ）7.任意一棵二叉树中的度可以小于2。（ ）8.树形结构最适合用来表示元素之间具有分支层次关系的数据。（ ）9.当采用分块查找时，数据的组织方式为：数据分成若干块，每块内数据必须有序。（ ）10.顺序查找法适合于存储结构为顺序存储或链式存储的线性表。（ ）四、应用题（本小题共5小题，每小题6分，共30分）1. 下面是对二叉树进行操作的算法，其功能为 （6分）Void unknown(Btree BT)Btree p=BT,temp;If(p!=NULL) temp=p->lchild;p->lchild=p->rchild;p->rchid=temp;unknown(p->lchild);unknown(p->rchild); 2. 请写出如图4.1所示二叉树的先序遍历序列、中序遍历序列和后序遍历序列。（6分）图4.1 二叉树3已知如图4.2所示的有向图，请给出：（共6分） 每个顶点的入度和出度；（2分）图4.2 有向图 邻接矩阵；（4分）4.要求用普里姆算法画出如图4.3所示无向网的最小生成树，假设从a顶点出发构造最小生成树，写出各条边加入生成树的次序（用权值表示）。（6分）图4.3 无向网 5.下列算法的运行结果是 （栈的元素类型为char）(6分)void main() stack S;char x=a,y=b;initstack(S);push(S,x); push(S,y); printf(“%c”,x);printf(“%c”,y);pop(S,x); pop(S,y); printf(“%c”,x); printf(“%c”,y);五、算法设计题（本大题共1小题，每题10分，共10分）1. 已知查找表的数据元素类型如下：Typedef struct Rectypeint num;char name8;Rectype; 假设查找表中有n个记录，并且是采用顺序存储Typedef Rectype Sqlist100;要求：（1）写出对给定值K进行从前端开始顺序查找的算法和main函数。（2）顺序查找算法的函数头部为“int search(Sqlist R,int n,int K) “（3）在main函数中建立该查找表、调用顺序查找算法，并输出查找结果。 数据结构 （A卷）试题标准答案及评分标准一、单项选择题（ 本大题共15小题，每小题2分，共计30分）1.B 2.B 3.C 4.A 5.A 6.B 7.C 8.B 9.B 10.C11.A 12.B 13.D 14.D 15.C 二、填空题（本大题共10个空，每空2分，共计20分）1.对象2.q->next=s,s->net=p3.数据4.（b,c,d）5.2k-1 6.v1,v3,v4,v6,v2,v5,v77.n-18.邻接矩阵，邻接表（不分先后）三、判断题（本大题共10小题，每小题1分，共计10分）1.× 2.× 3. 4. 5.× 6. 7. × 8. × 9. 10.×四、应用题（本大题共5小题，每小题6分，共30分）1利用栈将队列中的元素逆置（6分） 2.（6分） 3. （6分）其中：哈夫曼树（2.5分） 哈夫曼编码（3.5分）a:10 b:110 c:111 d:0111 e:00 f:0110 g:0114.（6分）其中深度优先搜索序列为v1,v2,v3,v6,v5,v4 (3分)广度优先搜索序列为v1,v2,v5,v4,v3,v6 (3分) 5.（6分）五、算法设计题（10分）int binsearch(Sqlist R,int n,int K) （5分）int low=0,high=n-1,mid;while(low<=high) mid=(low+high)/2; if(Rmid.key=K) return mid;else if(Rmid.key>K) low=mid+1; else high=mid-1; return -1; main() (5分) Sqlist R ;int n,k,i;scanf(“%d”,&n);for(i=0;i<n;i+)/*按num升序输入数据*/scanf(“%dn”,&Ri.num); gets(Ri.name); scanf(“%d”,&k);i=binsearch(R,n,k);if(i=-1) printf(“nof found!”); else printf(“found!”); 荆楚理工学院成人高等教育期末考试 数据结构 （B卷）试题标准答案及评分标准一、单项选择题（本大题共15小题，每小题2分，共计30分）1.A 2.B 3.A 4.A 5.C 6.C 7.A 8.B 9.A 10.B11.A 12.A 13.C 14.C 15.C 二、填空题（本大题共10个空，每空2分，共计20分）1.存储（物理）2.q=p->next,p->next=q->next 3.a4.长度 5.86.拓扑排序7.深度优先搜索遍历，广度优先搜索遍历（不分先后）8.6 三、判断题（本大题共10小题，每小题1分，共计10分） 1. 2. 3.× 4.× 5.× 6.× 7. 8. 9. × 10.四、应用题（本大题共5小题，每小题6分，共30分）1（6分）将二叉树中的左右子树交换 2.（6分）其中先序遍历序列为ABEFCDG（2分）中序遍历序列为EFBCGDA（2分） 后序遍历序列为FEGDCBA（2分）3.（2分 4分,共6分）4. （6分） (最小生成树4分，次序2分，共6分) 次序：1,4,3,9,235.abba （6分）五、算法设计题（10分）int search(Sqlist R,int n,int K) (5分)int i;for(i=0;i<n&&Ri.key!=K;i+);return i; main() （5分） Sqlist R ;int n,k,i;scanf(“%d”,&n);for(i=0;i<n;i+) scanf(“%dn”,&Ri.num); gets(Ri.name); scanf(“%d”,&k);i=search(R,n,k);if(i>=n) printf(“nof found!”);else printf(“found!”); 专心-专注-专业