《数据结构试题A.doc》由会员分享，可在线阅读，更多相关《数据结构试题A.doc（4页珍藏版）》请在金锄头文库上搜索。
1、注意：试卷中涉及的各种数据结构的类定义如下，请考生答题时参考。1链表结点类和链表类定义：template struct Node T data; Node *next; /此处也可以省略;template class LinkList public: LinkList( ); /建立只有头结点的空链表 LinkList(T a , int n); /建立有n个元素的单链表 LinkList(); /析构函数 void Insert(int i, T x); /在单链表中第i个位置插入元素值为x的结点 T Delete(int i); /在单链表中删除第i个结点 void PrintList(
2、); /遍历单链表，按序号依次输出各元素 private: Node *first; /单链表的头指针;2 二叉树类基本定义:template struct BiNode /二叉树的结点结构 T data; BiNode *lchild, *rchild;template class BiTreepublic: BiTree( ); /构造函数，初始化一棵二叉树，其前序序列由键盘输入 BiTree(void); /析构函数，释放二叉链表中各结点的存储空间BiNode* Getroot(); /获得指向根结点的指针 void PreOrder(BiNode *root); /前序遍历二叉树 vo
3、id InOrder(BiNode *root); /中序遍历二叉树 void PostOrder(BiNode *root); /后序遍历二叉树 void LeverOrder(BiNode *root); /层序遍历二叉树private: BiNode *root; /指向根结点的头指针 BiNode *Creat( ); /有参构造函数调用 void Release(BiNode *root); /析构函数调用 ;3图的邻接表类定义：const int MaxSize=12; struct ArcNode /定义边表结点 int adjvex; /邻接点域 ArcNode *next;
4、/指向下一个边结点的指针;template struct VertexNode /定义顶点表结点 T vertex; /顶点的名称 ArcNode *firstedge; /边表的头指针;template class ALGraphpublic: ALGraph(T a ,int n,int e);/构造函数，初始化一个有n个顶点e条边的图 ALGraph(); /析构函数，释放邻接表中各边表结点的存储空间 T GetVex(int i); /取图中第i个顶点数据信息 void DFSTraverse(int v); /深度优先遍历图 void BFSTraverse(int v); /广度优
5、先遍历图private: VertexNode adjlistMaxSize; /存放顶点表的数组 int vertexNum, arcNum; /图的顶点数和边数;阅卷人得分一 填空题（每空1分，计12分）1、_是数据的最小单位，_是讨论数据结构时涉及的最小数据单位。2、设一棵完全二叉树具有100个结点，则此完全二叉树有 个度为2的结点。3、在用于表示有向图的邻接矩阵中，对第i列的元素进行累加，可得到第i个顶点的_度。4、给定序列100， 86， 48， 73， 35， 39， 42， 57， 66， 21，按堆结构的定义，则它一定_堆。5、串的长度是指_。6、对于双向链表，在两个结点之间插
6、入一个新结点需要修改的指针共_个。 删除一个结点需要修改的指针共_个。7、已知广义表LS=(a,(b,c,d),e)，它的深度是_，长度是_。8、在8阶B-树中根结点所包含的关键码个数最多为_个。9、循环队列的引入是为了克服_。二 单项选择题（每题1分，计10分）1、线性表采用链接存储时，其地址（ ）。 A.必须是连续的 B.部分地址必须是连续的C.一定是不连续的 D.连续与否均可以2、栈和队列是两种特殊的线性表，只能在它们的（ ）处添加或删除结点。 中间点 端点 随机存取点 结点3、输入序列为ABC，可以变为BAC时，经过的栈操作为（ ）。A. push,pop,push,pop,push,
7、pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop4、下面（ ）不是算法所具有的特性。 有穷性 确切性 高效性 可行性5、下面关于串的的叙述中，（ ）是不正确的？A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储6、数组A67的每个元素占五个字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A35的地址是( )。 A. 1130 B. 1180 C. 1205 D. 12107、
8、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。An B(n-1)2 Cn-1 Dn28、若广义表A满足Head(A)=Tail(A)，则A为（ ）。A（ ） B（） C（），（） D（），（），（）9、堆的形状是一棵 ( )。 A.二叉排序树 B.满二叉树 C.完全二叉树 D.判定树10、若要在单链表中的结点 *p 之后插入一个结点 *s ，则应执行的语句是 ( ) As-next=p-next； p-next=s； Bp-next=s； s-next=p-next；Cp-next=s-next； s-next=p； Ds-next=p； p-next=s-next
9、；下列广义表中，长度为2的有（ ）1(a，b) 2(c，(a，b)，d) 3(c，(a，b) 4(a，b)，(c，(a，b)A.1B.1，3C.1，2D.1，2 ，3，4你可以出这题，只供参考1D 23C4C 56A 7D 8B 9C 10阅卷人得分三 应用题（每小题6分，计48分）1、已知广义表A=（1，2），（3，4，5），用求表头和表尾操作head( )和tail( )将原子元素4从A中取出来。2、设A为n阶对称矩阵(A=(aij)，1i，j n)，设计压缩存储方案，画出压缩存储方案图示，写出该压缩存储方案中矩阵元素aij的一维下标变换公式。要求结合图示说明。3、已知图G=（V, E），
10、其中V=v1,v2,v3,v4,v5, E=, , , ), ；画出这个图的图形并写出所有的拓扑序列。4、已知一棵二叉树的前序序列和中序序列分别为ABDFCEGH和BFDAGEHC，请画出此二叉树逻辑结构图示，并写出后序遍历序列。5、已知图G=（V, E），其中V=v1,v2,v3,v4,v5,v6,v7, E=(v1,v2), (v1,v3), (v1,v4), (v2,v5), (v3,v6), (v3,v5), (v4,v6), (v4,7), (v5,v6) , (v5,v7) , (v6,v7) ；画出这个图的图形表示和它的邻接表存储结构,并以该邻接表为存储结构，分别写出它的深度、广
11、度优先遍历序列。(从结点v1开始)。6、一个线性表为 B= （ 12 ,23 ,45 ,57, 20 ,03 ,78 ,31 , 15 ,36 ），设散列表为 HT0.12 ，散列函数为 H( key )= key % 13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 7、已知一组键值序列为(46 ，79 ，56 ，38 ，40 ，80, 95 ，24)，试采用快速排序法对该组序列作降序排序，并给出每一趟的排序结果。8、用序列（55， 31， 11， 37， 46， 73， 63， 02）建立一个平衡二叉排序树，简单用图描述构建过程，画出该树。阅卷人得分四
12、、算法题（40分）1、 阅读算法（每小题5分，计10分） （1）说出下列算法的功能，它是采用什么结构实现的。 template void BiTree:Unknown (BiNode *root) const int MaxSize = 100; int front = 0; int rear = 0; BiNode* QMaxSize; BiNode* q;if (root=NULL) return;elseQrear+ = root;while (front != rear)q = Qfront+; coutdatalchild != NULL) Qrear+ = q-lchild;if (q-rchild != NULL) Qrear+ = q-rchild; （2）根据下列算法和输入的数据画出生成的链表形式。templ
