笔试题目

数据结构类笔试题

数据结构类笔试题 一、选择题：15 分 共 10 题 1. 已知一个线性表(38,25,74,63,52,48)，采用的散列函数为 Hash($Key)=$Key mod 7，将元素散列到表长为7的哈希表中存储。请选择后面两种冲突解决方法分别应用在该散列表上进行等概率成功查找的平均查找长度，拉链法 ，线性探测法 . A. 1.0 B. 1.5 C. 1.7 D. 2.0 E. 2.3 F. 7/6 G. 4/3 H. 3/2 2. 需要将OS缓冲区的数据刷新到硬盘，可以调用的函数有(多选)： A.fflush() B. fsync() C. sync() D.writev() 3. 下面哪个shell语句不能打印出用户主目录的路径？ A. echo $HOME B. echo ~ C. echo `$HOME` D. echo $HOME 4. 最坏情况下，合并两个大小为n的已排序数组所需要的比较次数 A.2n B.2n-1 C.2n 1 D.2n-2 5. 一个B类网的子网掩码是255.255.240.0，这个子网能拥有的最大主机数是： A. 240 B. 255 C.4094 D. 65534 6. 以下代码执行后，val的.值是___: unsigned long val = 0; char a = 048; char b = 052; val = b 8 | a; A 20992 B 21064 C 72 D 0 7. 内存的速度远远高于磁盘速度，所以为了解决这个矛盾，可以采用： A 并行技术 B 虚存技术 C 缓冲技术 D 通道技术 8. 以下代码打印的结果是（假设运行在i386系列计算机上）： struct st_t { int status; short* pdata; char errstr[32]; }; st_t st[16]; char* p = (char*)(st[2].errstr 32); printf(%d, (p - (char*)(st))); A 32 B 114 C 120 D 1112 9. 同一进程下的线程可以共享以下 A. stack B. data section C. register set D. thread ID 10. 以下哪种操作最适合先进行排序处理？ A 找最大、最小值 B 计算算术平均值 C 找中间值 D 找出现次数最多的值 ;

数据结构笔试题

第一部分 选择题 一 单项选择题（本大题共 小题 每小题 分 共 分）在每小题列出的四个选项中只有一个选项是符合题目要求的 请将正确选项前的字母填在题后的括号内 算法分析的目的是( ? C? ) A 找出数据结构的合理性 B 研究算法中的输入/输出关系 C 分析算法的效率以求改进 D 分析算法的易读性 在需要经常查找结点的前驱与后继的场合中 使用(? B )比较合适 A 单链表 B 双链表 C 顺序表 D 循环链表 下面关于线性表的叙述中 错误的为(? D ? ) A 顺序表使用一维数组实现的线性表 B 顺序表必须占用一片连续的存储单元 C 顺序表的空间利用率高于链表 D 在链表中 每个结点只有一个链域 带头结点的单链表head为空的判断条件是( B ) A head=NIL ? B head >next=NIL C head >next=head ? D headNIL 队列通常采用两种存储结构是( A ) A 顺序存储结构和链表存储结构 B 散列方式和索引方式 C 链表存储结构和数组 D 线性存储结构和非线性存储结构 按照二叉树的定义 具有 个结点的二叉树有(? C? )种 A ? B ? C ? D 二叉树的结构如下图所示 其中序遍历的序列为( ? ) A a b d g c e f h B d g b a e c h f C g d b e h f c a D a b c d e f g h 深度为 的二叉树至多有(? C? )个结点 ( ^M ) A ? B ? C ? D 对于一个具有n个顶点的无向图 若采用邻接表表示 则存放表头结点的数组的大小为 (? A? ) A n ? B n+ ? C n ? D n+边数 在一个具有n个顶点的无向图中 要连通全部顶点至少需要(? C? )条边 A n ? B n+ ? C n ? D n/ 静态查找表与动态查找表二者的根本差别在于(? B? ) A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址 因为散列函数不是一对一的关系 所以选择好的( ?D? )方法是散列文件的关键 A 散列函数 ? B 除余法中的质数 C 冲突处理 ? D 散列函数和冲突处理 对于大文件的排序要研究在外设上的排序技术 即( C? ) A 快速排序法 ? B 内排序法 C 外排序法 ? D 交叉排序法 设有 个无序的元素 希望用最快的速度挑选出其中前 个最大的元素 最好选用(? C? )法 A 冒泡排序 B 快速排序 C 堆排序 D 基数排序 二 判断题(判断下列各题 正确的在题干后面括号内打 √ 错误的打 × 每小题 分 共 分) 所谓数据的逻辑结构指的是数据元素之间的逻辑关系 ( ? ) 在线性结构中 每个结点都有一个直接前驱和一个直接后继 ( ? ) 插入和删除是数组的两种基本操作 ( ? ) 在链栈的头部必须要设置头结点 ( ? ) 在二叉树中插入结点则该二叉树便不再是二叉树 ( ? ) 查找表的逻辑结构是集合 ( ? ) 静态查找表的检索与修改被分成两个不交叉的阶段分别进行 ( ? ) 在索引顺序文件中插入新的记录时 必须复制整个文件 ( ? ) 如果某种排序算法是不稳定的 则该方法没有实际的应用价值 ( ? ) 对于n个记录的集合进行冒泡排序 在最坏情况下所需要的时间是 (n )( ? ) 三 填空题(每小题 分 共 分) 程序设计的实质是________和________ 设由字符串a=′data′ b=′structure′ c=′ ′ 则a与c连接然后与b连接的结果为 ________ 通常单链表的头结点指的是________ 单链表的首结点指的是________ 一个队列的入队序列是a b c d 则队列的输出序列为________ 栈结构通常采用的两种存储结构是________和________ 具有N个结点的完全二叉树的深度为________ 树的三种主要的遍历方法是 ________ ________和层次遍历 在无向图的邻接矩阵A中 若A〔i j〕等于 则A〔j i〕等于________ 采用散列技术实现散列表时 需要考虑的两个主要问题是 构造________和解决________ 索引顺序表上的查找分两个阶段 ( )________ ( )________ 散列文件中的记录通常是成组存放的 若干的记录组成一个存储单位 称作________ 就文件而言 按用户的观点所确定的基本存储单元称为________ 按外设的观点所确定的基本存储单元称为________ 文件的检索有三种方式 ________存取 ________存取和按关键字存取 最简单的交换排序方法是________排序 外排序的基本方法是________ 四 应用题(每小题 分 共 分) 假定在学生的档案中含有 姓名 学号 年龄 性别 如采用线性表作为数据结构来实现档案管理问题 分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义 有一份电文 *** 使用五个字符 a b c d e 它们的出现频率依次为 请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权) 求出每个字符的哈夫曼编码 有初始的无序序列为{ } 给出对其进行归并排序(升序)的每一趟的结果 五 设计题(每小题 分 共 分) 假设用一个循环单链表来表示队列(称为循环链队) 该队列中只设一个队尾指 针rear 不设队首指针 请编写向循环链队中插入一个元素X的过程 以邻接表为存储结构 写出连通图的深度优先搜索算法 设有一组关键字{ } 采用散列函数 H(key)=key MOD 采用线性探测法解决冲突 试在 ～ 的散列地址空间中对该关键字序列构造散列表 数据结构导论试题参考答案 一 单项选择题(每小题 分 共 分) ? C ? B ? D ? B ? A C ? B? C ? A ? C B D C C 二 判断题(每小题 分 共 分) × ? × ? × × ? × √ ? √ ? × × √ 三 填空题(每小题 分 共 分) ? ( )数据表示? ( )数据处理 ? ′data structure′ ? ( )在单链表第一个结点之前增设的一个类型相同的结点 ( )表结点中的第一个结点 ? a b c d ? ( )顺序存储结构? ( )链表存储结构 〔log N〕+ ( )先根遍历? ( )后根遍历 ( )散列函数? ( )冲突 ( )确定待查元素所在的块 ( )在块内查找待查的元素 桶 ( )逻辑结构 ? ( )物理结构 ( )顺序? ( )直接 冒泡排序 ? 归并 四 应用题(每小题 分 共 分) ? 顺序实现 const maxsize∶= ; ｛顺序表的容量｝ ? type datatype=record ｛档案数据类型｝ name∶string〔 〕;｛姓名｝ number∶integer;｛学号｝ sex∶boolean;｛性别｝ age∶integer;｛年龄｝ end; type slist =record data∶array 〔 maxsize〕 of datatype; last∶integer; end; 链接实现 type pointer=↑node; node=record name∶string 〔 〕;｛姓名｝ number∶interger ｛学号｝ sex∶ boolean;｛性别｝ age∶integer;｛年龄｝ next∶pointer;｛结点的后继指针｝ end; list=pointer; 哈夫曼树为 相应的哈夫曼编码为 a: ? b: ? c: ? d: ? e: 画出正确的哈夫曼树给 分 写出相应哈夫曼编码给 分 初始无序序列 ? ? ? ? ｛ ｝ ｛ ｝ ｛ ｝ ｛ ｝ ｛ ｝ ｛ ｝ ｛ ｝｛ ｝ ｛ ｝｛ ｝ 第一次归并 ｛ ｝ ｛ ｝ ｛ ｝? ｛ ｝? ｛ ｝ 第二次归并 ? ｛ ? ? ｝ ｛ ? ｝? ｛ ｝ 第三次归并 ｛ ? ｝? ｛ ｝ 第四次归并 ｛ ? ? ｝ 五 设计题(每小题 分 共 分) PROCEDURE insert (VAR rear∶pointer; x∶integer); VAR head tmp∶pointer; BEGIN new(tmp); tmp↑ data∶=x; if (rear=NIL) then ｛循环队列为空 新结点是队列的首结点｝ BEGIN rear∶=tmp; rear↑ next∶=tmp; END else ｛队列不空 将新结点插入在队列尾｝ BEGIN head∶=rear↑ next; rear↑ next∶=tmp; rear∶=tmp; rear↑ next∶=head; END END; procedure dfs(g:adj list;v ∶integer); ｛从v 出发 深度优先遍历图g｝ begin write(v ); visited(v )∶=true; ? ｛标志v 已访问｝ p=g〔v 〕 link; ? ｛找v 的第一个邻接点｝ while pnil do 〔 if not (visited〔p↑ vertex〕) then dfs(g p↑ vertex); p∶=p↑ next〕 ｛找v 的下一个邻接点｝ end; 以邻接表为存储结构 连通图的深度优先搜索就是顺序查找链表 构造过程如下 H( )= MOD = H( )= MOD = H( )= MOD = H( )= MOD = (冲突) H( )=( + ) MOD = H( )= MOD = H( )= MOD = H( )= MOD = (冲突) H( )=( + ) MOD = (仍冲突) H( )=( + ) MOD = H( )= MOD = (冲突) H( )=( + ) MOD = (冲突) H( )=( + ) MOD = (仍冲突) H( )=( + ) MOD = H( )= MOD = (冲突) H( )=( + ) MOD = (仍冲突) H( )=( + ) MOD = H( )= MOD = H( )= MOD = (冲突) H( )=( + ) MOD = (仍冲突) H( )=( + ) MOD = H( )= MOD = (冲突) H( )=( + ) MOD = 因此 各关键字相应的地址分配如下 address( )= address( )= address( )= address( )= address( )= address( )= address( )= address( )= address( )= address( )= address( )= address( )= lishixinzhi/Article/program/sjjg/201404/30585

CLUB笔试题分享

CLUB笔试题分享 　　CLUB智力类笔试题分享： 　　1. 6个硬币加起来为0.41元，可能的面值为1分、5分、10分和25分。是否能肯定其中三个必为1角（1角为10分）？ 　　2. a比b快，c比a慢。不能判断b和c谁快谁慢是对是错？2. 6个硬币加起来为0.41元，可能的面值为1分、5分、10分和25分。是否能肯定其中三个必为1角（1角为10分）？3. 三个单词：dos、tam、man相叠加书写。dos在最上面，tam在中间，man在最下面。问：能否找出nad和mas这1. a比b快，c比a慢。不能判断b和c谁快谁慢是对是错？ 　　3. 三个单词：dos、tam、man相叠加书写。dos在最上面，tam在中间，man在最下面。问：能否找出nad和mas这两个单词？ 　　4. 从起点向西走1个单位，向南走2个单位，再向东走1个单位后，距起点的距离是否是2个单位？ 　　5. 有三种颜色涂一个立方体，每一面一种颜色。问：能否让相邻两面均为不同种颜色？ 　　6. 一个正八边形（ regular octagon），能否用4条直线分成8个三角形？ 　　7. 三个大小相同的圆互相重叠，能否划分出九个区域？ 　　8. 从第b页开始看，看到第e页，问：一共看了几页？ 　　9. a、b、c、d四本书放在书架上，b在c的左侧。如果b和c相邻，则d和b一定也相邻。问：共有几种可能的摆放顺序？ 　　10. 一群老太太带着她们的猫在屋中聚会，共22个头和72只脚。问：有多少老太太，多少只猫？ 　　11. 一只原本戴在右手的'手套从里向外翻出（inside-out）后，能否戴在左手？ 　　12. 选出与其它几项不同的一项：（1）a;（2）z;（3）n;（4）f;（5）e。 　　13. 寻找规律填写：3968，63，8，3， 。 　　14. 寻找规律填写：k，w，x，y，j，t，u，v，i，q，r，s， ， ， 。 　　15. 6个分散的任意点，两两相连，需多少根线？ 　　16. 某商品降价20%，问现在要涨百分之多少才能恢复到原来的价格水平？ 　　17. 7个芭蕾舞演员跳8小时，共消耗20单位热量。现在若只跳4小时，仍消耗20单位热量，需多少新加入者？（新加和者消耗热量数为原演员的一半）18. john和tom赛跑，从a点跑到b点，再从b点折回a点。john从a到b的速度为24，从b返回a的速度为16;tom往返速度均为20。问：谁先返回a点？ 　　19. 两个数相加为110，其中一个为另一个的150%，求：两个数各为多少？ 　　20. 某人卖掉两张收藏卡，每张600元。其中一张搛了20%，另一张亏了20%。问：他总体是盈是亏？盈/亏多少？ 　　21. 从1到100这100个自然数中，数字9共出现了几个？ 　　22. 某俱乐部中，男性会员占80%，游泳爱好者占70%，网球爱好者占60%。问：既是游泳爱好者，又是男性网球爱好者的至少占多少？ 　　23.1到15按顺序排列，问相邻两个数字相加是否偶数？（关键是要知道奇数英文是odd number，偶数是even number）24.按规律填数：1，3，6，10，____ 　　25. 12 9 _____ 　　2 6 8 3 4 5 　　26.小明帮老师去拿球，一共要拿15个，小明一次拿3个，要跑几次？ 　　25.open-ended的篱笆长100米，两根柱子之间隔20米，问需要几根柱子？ 　　26.小红吃威化饼干，吃了1块后将剩余的一半给小明，小明吃了1块后，他还有2块，问小红原来有几块？ 　　27.一根箭从左到右要转几度？ 　　28.谣言d和e之间互传，然后另一途径是a到b到c到e（不可逆），问如果谣言从b开始传，有谁不知道？ 　　29.a欠b$64，a自己有$28，c又借给a$28，问a是不是可以把钱还清？ 　　30.某人是班级里的正数第16名和倒数第16名，问该班是不是共有32人？ 　　31.5个厨师花1小时可以做一顿饭，问4个厨师做一顿饭需要花多少分钟？ 　　32.与discord相反意思的词是哪一个？ supportive，agreement……33.stoke and smother的关系 相当于… 　　34.与club和golf关系一样的有：glove和baseball，ball和soccer，type和book，board和chess…35.和facilitate意思最近的单词foil，expedite，extol，…36.gratuitous的反义词… 　　37.不符合规律的数字：64，54，42，31，20 　　38.所有的a都是b，c是a，所以c是b 　　39.虽然这次的矛盾被平息了（意见达成一致了），但是从以往的经验来看，结果并不乐观，然后根据句意理解选一个单词（gre填空原题） ;