《2022年数据结构期末试题与答案宣贯 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构期末试题与答案宣贯 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 1 页，共1 页仲 恺 农 业 工 程 学 院 试 卷（答案及评分标准）数据结构与算法2011至 2012 学年度第2 学期期 末 （A）卷专业班级姓名学号（考生注意：考试时间为120 分钟。答案须写在答题纸上，并注明题号，考试结束后将试卷连同答题纸一齐交）一、选择题（每小题选出一个最合适的答案，共30 分）1、在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（C）A数据元素的相邻地址表示B数据元素在表中的序号表示C指向后继元素的指针表示D数据元素的值表示2、线性表采用链式存储时，结点的存储地址（B）A必须是不连续的B连续与否均可C必须是连续的D和头结点的存储地址相连续3、设数组
2、datam作为循环队列 SQ的存储空间， front 为队头指针，rear为队尾指针，则执行出队操作后其头指针front 值为（D）Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m 题 号一二三四五六七八合计得 分评卷人名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 第 2 页，共2 页Dfront=(front+1)%m 4、设有一个顺序栈S，元素 s1，s2，s
3、3，s4，s5，s6 依次进栈，如果 6 个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为多少（C）A1 B2 C3 D4 5、栈和队列都是（A）A限制存取位置的线性结构B顺序存储的线性结构C链式存储的线性结构 D限制存取位置的非线性结构6、现有一“遗传”关系：设x 是 y 的父亲，则 x 可以把它的属性遗传给 y。表示该遗传关系最适合的数据结构为（B）A线性表B树C图D二叉树7、下列陈述中正确的是（D）A二叉树是度为2 的有序树B二叉树中结点只有一个孩子时无左右之分C二叉树中必有度为2 的结点D二叉树中最多只有两棵子树，并且有左右之分8、在具有 n 个叶子结点的严
4、格二叉树（即结点的度要么是0 要么是2）中，结点总数为（C）A2n+1 B2n C2n-1 D2n-2 9、N 个顶点的有向完全图中含有有向边的数目最多为（D）AN-1 BN CN(N-1)/2 DN(N-1) 10、在含 n 个顶点和 e 条边的无向图的邻接矩阵中,零元素的个数为（D）Ae B2e Cn2e Dn22e 二、填空题（每小题4 分，共 20 分）1、栈顶的位置是随着进栈和出栈操作（栈操作）而变化的。2、 对于单链表形式的队列， 其空队列的 front指针和 rear 指针都等于头结点的地址。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -
5、 - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 第 3 页，共3 页3、n 个记录的折半查找，若查找失败，进行了log2n+1 次比较。4、从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需向前移动一个位置。5、在队列中，允许进行插入操作的一端称为队尾 ，允许进行删除操作的一端称为队头。三、给出线性表的单链表存储结构，并实现用e 返回线性表中第 i 个元素的值（即编写完整的函数GetElem(L,i,e)，这里只给出函数的名称和参数名，未给出类型） 。 （10 分）typedef struct LNode
6、ElemType data; struct LNode *next; LNode,*LinkList; Status GetElem(LinkList L,int i,ElemType &e) LinkList p; int j; p=L-next; j=1; while(p&jnext; +j; if(!p|ji)return ERROR; e=p-data; return OK; 四、给出单链队列的存储结构（数据类型名为LinkQueue） ，下面是入队函数，但有缺漏，请补全（说明在哪一行补什么内容）。 （10 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - -
7、- - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 第 4 页，共4 页Status EnQueue(LinkQueue Q,e) p=new QNode; if(!p) return 0; p data=e; Q.rear=p; return 1; typedef struct QNode QElemType data; struct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue
8、; Status EnQueue(LinkQueue &Q,QElemType e) QueuePtr p; p=new QNode; if(!p) return 0; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return 1; 五、给出二叉树的三叉存储结构，若二叉树后序遍历的序列为BDECA，请画出该二叉树。（10 分）typedef struct TrTNode TElemType data; struct TrTNode *lchild,*rchild,*parent; 名师资料总结 - - -精品资料欢迎下载 - - - - -
9、- - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 第 5 页，共5 页TrTNode,*TrTree; 六、假设通信电文使用的字符集为a,b,c,d,e,f ，名字符在电文中出现的频度分别为： 34，5，12，23，8，18，试为这 6 个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。（10分）a:11 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -
10、 - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 第 6 页，共6 页b:1010 c:100 d:01 e:1011 f:00 七、给出图的邻接多重表的存储结构，并说明其主要适用于存储何种图。 （10 分）typedef struct EBox VisitIf mark; int ivex,jvex; struct EBox *ilink,*jlink; InfoType *info; EBox; typedef struct VexBox VertexType data; EBox *firstedge; VexBox; typedef struct VexBox VexBox adjmulistMax_VERTEX_NUM; int vexnum,edgenum; AMLGraph; 这个结构主要适用于存贮无向图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -