《数据结构(同名4772)》由会员分享，可在线阅读，更多相关《数据结构(同名4772)（5页珍藏版）》请在金锄头文库上搜索。
1、数据结构一、单项选择题1 数据的最小单位是_A_。 A数据元素 B.记录 C.数据对象 D.数据项2. 对于一个具有n个结点和e条边的无向图，若采用邻接表表示，所有边链表中边结点的总数为_C_。A. e/2 B.e C.2e D.n+e3. 数组a1.6,1.5 （无0行0列）以列序为主序顺序存储，a11的地址为1000，每个元素占2个存储单元，则a34的地址是_A_。A.1026 B.1040 C.1042 D.10464. 某线性表常发生的操作为删除第一个数据元素和在最后一个元素后添加新元素，采用_D_的存储结构，能使其存储效率和时间效率最高。A单链表B仅用头指针的循环链表C双向循环链表D
2、仅用尾指针的循环链表5. 在一个单链表中，已知q所指向的结点是p指向的结点的直接前驱结点，若在q所指向的结点和p指向的结点间插入s所指向的结点， 则执行 C _ 。A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p;C. q-next=s; s-next=p; D. p-next=s; s-next=q;6. 若循环队列使用C数组Am存放其数据元素，已知头指针front指向队首元素，尾指针rear指向尾元素后的空单元，则当前队列中的元素个数为_A_。A.(rear-front+m)%m B. rear-front+1C. rear-fr
3、ont D. rear-front-17. 栈和队列的共同点是_C_。A.先进先出B. 后进先出C.只允许在端点处插入和删除元素D. 运算受限的线性表8. 一棵深度为5的完全二叉树，叶结点数最大值和最小值分别为_B_。 A. 10，5 B. 16，8 C. 8，4 D. 32，16 9. 折半查找有序表(5,15,25,35,40,65,70,75,80,85,88,90),若查找元素75,需依次与表中元素_A_进行比较,。 A.65,80,70,75 B.65,85,75 C.65,80,75 D.70,85,7510. 算法suanfa的时间复杂度为_A_。int suanfa(int n
4、) int i=1； while(pow(2,i)=n) /* pow(2,i)表示2i*/ i=i+1；return i； A.O(log n) B.O() C.O(n2) D.O(n)二、简答题 1. 简叙深度优先遍历算法与广度优先遍历算法的区别，当采用广度优先遍历时，如何记录已被访问的顶点？答：区别：可以看到两种方法最大的区别在于前者从顶点的第一个邻接点一直访问下去再访问顶点的第二个邻接点；后者从顶点开始访问该顶点的所有邻接点再依次向下，一层一层的访问。可以用队列来储存那些没有访问或者刚访问过的结点，对每个结点设置一个访问标志位。2.设文件R共有1500条记录，磁盘的读、写单位为250条
5、记录，内存可提供750条记录的空间，试简要说明对文件R的排序过程。答： 第一步，每次将三个记录块即750个记录有外存读到内存，进行内部排序，整个文件被分成2个有序子序列，然后分别把它们写到外存上去。 第二步，两两归并有序子文件，进行了一趟，最终成为了一个有序文件。三、画图题 1. 已知一链式队列中，队列元素依次为A,B,C,D, 完成删除操作3次，试画出每次删除之后的链式队列存储结构。 初始队列：front（队头指针） A B C D rear（队尾指针） 第一次：front（队头指针） B C D rear（队尾指针） 第二次：front（队头指针） C D rear（队尾指针） 第三次：f
6、ront（队头指针） D rear（队尾指针） 2. 已知一棵二叉树的先序遍历结果为ABCDEFG，中序遍历结果为CBEDAFG，试画出这棵二叉树。 A B F C D G E四、计算题1.设对18个记录的表作折半查找， (1)画出折半查找过程的判定树；(2)假定每个元素的查找概率相等,试计算查找成功时的平均查找长度。（1） 判定树 （2）ASL（成功）=（1*1+2*2+4*3+8*4+3*5）/18=32/9ASL（不成功）=（13*5+6*6）/13=101/132. 试用权值集合 12，4，5，6，1，2构造赫夫曼（Huffman）树，（1）列出构造过程，（2）计算该哈夫曼树的带权路径
7、长度。 初始集合： 12，4，5，6，1，2 第一次：选取1、2 集合： 12，4，5，6，3第二次：选取3、4 集合： 12，7，5，6第三次：选取5、6 集合： 12，7，11第四次：选取7、11 集合： 12，18第五次：选取12、18 集合：30 构造完成WPL=2*4+3*3+1*1=183.试用关键字序列(39,25,24,50,12,14,20,19,37,6),构造哈希(Hash)表,设哈希函数为:H(key)=key % 13,其中key为关键字,%为求余运算符；用开放定址法处理冲突, 用线性探测再散列法查找空位,用数组A15表示哈希表。 (1)画出该哈希表的存储结构图；(2
8、)假定每个元素的查找概率相等, 计算查找成功及查找失败时的平均查找长度。01234567891011123912143719205062425ASL(成功)=(1+1+1+1+3+2+1+1+6+4)/10=2.1ASL(不成功)=（5+4+3+2+1+1+5+4+3+2)/10=3.0五、算法设计题1. 设a 的初值为（119，527，9，768，22，549）a0为临时工作单元。分析如下程序段：for (i=0,d=1;i3; i+,d*=10) for ( j=0; j10; j+) countj=0; for( j=0; j6; j+) count aj / d % 10+; for ( j=1; j=0; j- -) b- -countaj / d % 10=aj; for( j=0; jnext;L-next=NULL;while(p)q=p;p=p-next;q-next=L-next;L-next=q;return OK;考虑到公司仍有部分低层及高层人员的补充，因此在选择招聘渠道供应商的附加值时以配送普工现场招聘会和高端人才交流会为佳，另外根据供应商平台实力，若能给公司提供合适的猎头服务也应当纳入甄选范畴。
