《2004数据结构考试试卷》由会员分享，可在线阅读，更多相关《2004数据结构考试试卷（10页珍藏版）》请在金锄头文库上搜索。
1、承诺：我将严格遵守考场纪律，并知道考试违纪、作弊的严重性，承担由此引起的一切后果。专业 班级 学号 学生签名： 承诺：我将严格遵守考场纪律，并知道考试违纪、作弊的严重性，承担由此引起的一切后果。专业 班级 学号 学生签名： 华东交通大学 2004 2005 学年第 1 学期考试卷 数据结构 课程 课程类别：必修 闭卷题号一二三四五六七八九总 分分数评卷人一， 填空题（每空1分，共20分）1， 现有一个程序，它能够处理气象卫星收集的数据用来预测今后两天的天气，但是却要算上将近一个星期，故其在实践中应该来讲是没有什么意义的，不能称其为算法，因为它违背了算法的_可行性_。2， 若设L是带表头结点的单
2、链表的表头指针，则语句L-next= L-next-next的作用是_删除单链表的第一个结点_。（其中next是节点指针域）3， 我国的权力机构由各级人民代表大会组成，如果将所有代表大会当作一个数据整体，则根据我国的实际管理关系，用数据结构里面的术语，它们之间是_树状_关系。4， 在线性表的顺序存储实现中，假设线性表的长度为n，则平均插入一个数据元素平均要移动元素的次数为_n/2_。（假设元素插入到各个位置的概率相同）5， 后缀表达式“4 5 * 3 2 + - 4 -”的值为_11_。（注意所有数都为1位个位数）6， 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈
3、，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为_3_。7， 设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用步长为5,3,1的Shell排序法，则进行到步长为3之后，执行步长为1之前的结果是_A,D,C,M,H,F,Q,Q,X,R,S,Y_；若采用以最后一个元素为分界元素的快速排序法，则一趟扫描的结果是_Q,H,C,F,Q,A,M,S,R,D,X,Y_。8， 一个具有567个结点的完全二叉树，其叶子结点个数为_284_。 9， 一颗二叉树有13个结点，则这颗二叉树的高度最大为_14_,最小
4、为_4_。10， 在AOV网中，顶点表示_活动_，边表示_活动间优先关系_。11， 哈希表的装填因子含义_哈希表的装满程度_。12， 有一个整数有序序列（4，6，8，34，45，67，89，123），若采用二分查找，则查找89要进行_3_次比较。13， 一颗二叉树的叶结点分别为（4，6，7，2，5，67），则这颗树有_5_个度为2的结点。14， 用邻接矩阵存储图，占用存储空间数与图中顶点个数_有_关，与边数_无_关。二， 选择题（每题2分，共20分）1，一种抽象数据类型包括数据和（ B ）两个部分。A. 数据类型B. 数据操作C. 数据抽象D. 类型说明 2，设循环队列中数组的下标范围是0.n
5、-1，其头尾的下标分别为f和r，则其元素个数为（ A ）。A、(r - f+n) % n B、(r - f) % n+1 C、r - f+1 D、r - f3, 由权值分别为3，8，6，2，2的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ C ）A 14 B 44 C 45 D 214, 以下序列中不符合堆定义的是_D_。 A(102，87，100，79，82，62，84，42，22，12，68) B(102，100，87，84，82，79，68，62，42，22，12) C(12，22，42，62，68，79，82，84，87，100，102) D(102，87，42，79，82，62，6
6、8，100，84，12，22)5, 解决散列法中出现的冲突问题常采用的方法是（ D ）。A. 数字分析法、除留余数法、平方取中法B. 数字分析法、除留余数法、线性探测法C. 数字分析法、线性探测法、双散列法D. 线性探测法、二次探测法、开放地址拉链法6, 设双向循环链表中结点的结构为（data, lLink, rLink），且不带表头结点。若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作？（ D ）A. p-rLink = s; s-lLink = p; p-rLink-lLink = s; s-rLink = p-rLink;B. p-rLink = s; p-rLink-
7、lLink = s; s-lLink = p; s-rLink = p-rLink;C. s-lLink = p; s-rLink = p-rLink; p-rLink = s; p-rLink-lLink = s;D. s-lLink = p; s-rLink = p-rLink; p-rLink-lLink = s; p-rLink = s;/7,设有一个nn的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A00存放于B0中，那么第i行的对角元素Aii存放于B中（ ）处。A. (i+3)*i/2B. (i+1)*i/2C. (2n-i+1)*i/2D. (2n-i-1)*i/2/8
8、，给定一个字符串“ababaa”,则这个串对应nextval函数值分别为（D ） A,012324 B，010104 C，010105 D，0112349, 为了实现图的广度优先遍历，BFS算法一般需要使用的一个辅助数据结构是（ B ）。A. 栈 B. 队列C. 二叉树 D. 树10, 对于如图所示的带权有向图，从顶点1到顶点8的最短路径为（ C ）。 A. 59B. 51 C. 50D. 60三，程序阅读题（每题6分，共24分）1， 数据结构link的定义如下，函数visit用于打印参数所指向的结点数据，请指出函数unknown的作用是什么，其中的参数h代表如下图所示的一个单链表，写出输出结
9、果。typedef struct LinkNodeint data;struct LinkNode *next;*link;void unknown(link h, void (*visit)(link) if (h = NULL) return; unknown(h-next, visit);(*visit)(h); 作用：逆序输出链表中的结点结果：E R A2， 此算法用到了一个整数堆栈，其中InitStack，Push，Pop，StackEmpty分别代表堆栈初始化、进栈、出栈和判断堆栈是否为空，请说出此算法的作用，当输入的n和r的值分别为15和5时，写出输出结果。void unknow
10、n()Stack s;int e;int n,r;InitStack(s);cout请输入变量r和nrn;if(r9|r2|n0)cout请重新输入变量r和nendl;goto again;while(n)e=n%r;Push(s,e);n=n/r;while(!StackEmpty(s)Pop(s,e);coute ;coutendl; 作用：把一个正整数，转换成29之间的进制数结果：303， 下图是一个AOV图，根据以下拓扑排序程序，写出输出的拓扑序列及拓扑排序的基本过程（注：如果能够确定写出的输出结果正确无误，可以省略后面的拓扑排序过程的描述） AOV图AOV图的邻接链表表示这一列代表初
11、始各节点的入度struct node int degree; struct node *link; ;typedef struct node NODE;int toposort(NODE adjlist , int num) /有向图采用邻接表存储结构。/若图无回路，则输出图的顶点的一个拓扑序列并返回1，否则0。 int stack100; /存放入度为0的顶点的栈 int i, top, out, k; NODE *p; int num1=0;top=0; for(i=0; i0) top-; out=stacktop; printf( “%d,”,out); num1+; p=adjlis
12、tout.link; while ( p!=NULL) k=p-degree; adjlistk. degree - -; /顶点入度减1， if(adjlistk.degree=0)/若入度减为0，则进栈 stacktop=k;top+; p=p-link; if (num1num) /根据输出节点数来判断 return( 0); /该有向图是否有回路 else return (1);拓扑排序的结果：V1,V0,V4,V3,V6,V2,V54， 知有向图的邻接矩阵表示及其一个算法描述如下：A =0 1 1 1 10 0 1 0 00 0 0 1 11 1 0 0 00 0 1 1 0const int MaxVertices = 5;struct Graph /图的邻接矩阵表示int EdgeMaxVerticesMaxVertices; /有向图邻接距阵int CurrentNode; /有向图当前结点数int CurrentEdges; /当前边数int unknown ( in
