数据结构 面试题 3
2024-05-06 11:18
1. 数据结构 面试题 3
一个算法通常由哪两种基本要素组成？ 答案 一是对数据对象的运算和操作 二是算法的控制结构 算法的复杂度主要包括什么？ 答案 时间复杂度和空间复杂度 实现算法所需的存储单元多少和算法的工作量大小分别称为算法的空间复杂度和时间复杂度 什么是数据处理？ 答案 所谓数据处理是指对数据集合中的各元素以各种方式进行运算 包括插入 删除 查找 更改等运算 也包括对数据元素进行分析 数据结构是指？ 答案 数据结构是指相互有关联的数据元素的集合 数据结构分为？ 答案 数据结构分为逻辑结构与存储结构 线性链表属于存储结构 数据结构包括？ 答案 数据结构包括数据的逻辑结构和数据的存储结构 数据元素之间的任何关系都可以用什么来描述？ 答案 用前趋和后继关系来描述 数据的逻辑结构分为哪两大类？ 答案 有线性结构和非线性结构两大类 常用的存储结构有？ 答案 顺序 链接 索引等存储结构 顺序存储方法是什么？ 答案 顺序存储是把逻辑上相邻的结点存储在物理位置相邻的存储单元中 栈的基本运算有哪三种？ 答案 入栈 退栈与读栈顶元素 队列主要有哪两种基本运算？ 答案 入队运算与退队运算 栈和队列通常采用的存储结构是？ 答案 链式存储和顺序存储 当线性表采用顺序存储结构实现存储时 其主要特点是？ 答案 逻辑结构中相邻的结点在存储结构中仍相邻 循环队列主要有两种基本运算？ 答案 入队运算与退队运算 每进行一次入队运算 队尾指针就进 当循环队列非空且队尾指针等于对头指针时 说明循环队列已满 不能进行入队运算 这种情况称为？ 答案 上溢 lishixinzhi/Article/program/sjjg/201405/30743
2. 数据结构笔试题
第一部分 选择题
一 单项选择题（本大题共 小题 每小题 分 共 分）在每小题列出的四个选项中只有一个选项是符合题目要求的 请将正确选项前的字母填在题后的括号内
算法分析的目的是( ? 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
3. 数据结构面试题
1. 数据结构的定义。 2. 栈的两个应用：括号匹配和表达式的计算。是怎么应用的？表达式计算用的是哪种表达方式？有什么好处? 3. 字符串匹配算法：朴素的匹配算法、KMP算法。 4. 二叉树前序、中序、后序递归遍历算法。二叉树前序非递归遍历算法。 5. 堆，建堆算法，堆的插入和删除算法，堆排序。 6. 哈希。哈希函数的有哪些种？余数的取法？ 处理冲突的方法？ 闭散列方法有哪些？ 7. 二叉搜索树的搜索、插入、删除。时间复杂度。 8. 二叉平衡树的插入结点的原理，有哪几种旋转方式？分别适用于哪种情况。分析二叉平衡树的时间复杂度。 9. 红黑树的定义，红黑树的性能分析和与二叉平衡树的比较。 10. 图有哪些储存表示。 11. 链表插入排序、链表归并排序。 12. 常见的有哪几种排序算法，试比较其时间复杂度，以及是否稳定，及各自使用的情形。 13. 常用分配排序有哪几种？ 基数排序的定义，分类及原理。 14. 外部排序的过程。 15. B树、B+树、Trie的概念及用途，添加删除结点的原理。
4. 数据结构类笔试题
数据结构类笔试题
一、选择题：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 找出现次数最多的值
;
5. 数据结构笔试题和答案
数据结构笔试题和答案
数据结构笔试题和答案：
1. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：
q=head;
while (q->next!=p) q=q->next;
s= new Node; s->data=e;
q->next= ; //填空
s->next= ; //填空
2. 线性表的顺序存储结构是一种 的存储结构，而链式存储结构是一种___的存储结构。
A.随机存取 B.索引存取 C.顺序存取 D.散列存取
3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。
A. 必须是连续的 B. 部分地址必须是连续的
C. 一定是不连续的 D. 连续或不连续都可以
4. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。
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;
5. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。
A. s->next=p; p->next=s; B. s->next=p->next; p->next=s;
C. s->next=p->next; p=s; C. p->next=s; s->next=p;
6. 在一个单链表中，若删除p所指结点的后续结点，则执行____。
A. p->next= p->next->next; B. p= p->next; p->next= p->next->next;
C. p->next= p->next; D. p= p->next->next;
7. 链表不具备的特点是 ____ 。
A 可随机访问任何一个元素 B 插入、删除操作不需要移动元素
C 无需事先估计存储空间大小 D 所需存储空间与线性表长度成正比
8. 以下关于线性表的说法不正确的是 。
A 线性表中的`数据元素可以是数字、字符、记录等不同类型。
B 线性表中包含的数据元素个数不是任意的。
C 线性表中的每个结点都有且只有一个直接前趋和直接后继。
D 存在这样的线性表：表中各结点都没有直接前趋和直接后继。
9. 在一个长度为n的顺序表中删除第i个元素，要移动 个元素。如果要在第i个元素前插入一个元素，要后移( )个元素。 N-I N-I+1
答案
1.q->next=s;
s->next=p;
2.A/C(这题是考察对概念的理解，可参考第7题，“顺序表才能随即存取，而链表不可以”)
3.D
4.C
5.B
6.A
7.A(此题绝对选A，因为链表只能根据他的前一个结点才能找到下一个结点，不具备随即访问元素的功能)
8.C
9.n-i; n-i+1
更多的相关笔试题目推荐：
融捷科java软件工程师技笔试题 运营维护工程师笔试题 中国银行计算机方向笔试题目
;
6. 数据结构笔试题怎么做啊
树可以看图，平均深度是2
7. 数据结构试题
答案是 度数为3的结点有14个。 假设： 三叉树中度为3的结点x个， 度为2的结点y个，度为1的结点z个，度为0的结点m个,总结点数sum sum = x+y+z+m 从另外一个角度看，除了根节点，树的每个结点上方都关联一个分支， 所以总结点数sum=分支数+1= 3x+2y+z+1（因为度数为3的结点有3个分支，度数为2的结点有2个分支，以此类推） 即 x+y+z+m= 3x+2y+z+1，消去等式两边的z，整理得 x+y+m= 3x+2y+1，将题目中已知条件带入（y=21,m=50）,求得x=14
8. 数据结构考试题
构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。 正确。第0个元素地址为100，则第i个元素地址为100+4*i，将12代入得148。 （ ）2.在任何一种线性链表上都无法进行随机访问。 错误。比如只要知道顺序表首地址和每个数据元素所占存储单元的个数，就可以求出第i个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存取的特点。 （ ）3.顺序栈是一种规定了元素进栈顺序的栈。 错误。按存储结构来分，堆栈分为顺序栈和链栈，其中栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表，却并没有规定元素进栈顺序。 （ ）4.循环列表中每一个元素都有后继。 正确。注意，这里可能有笔误，应写为“循环链表”而非“循环列表”。 （ ）5.删除一个二叉树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。 错误。 二.填空题。 6.下面程序的时间复杂度为___________。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 法则1：for循环：一个for循环的运行时间至多是该for循环内语句（包含测试）的运行时间乘以迭代的次数。 法则2：嵌套循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。 对于此处嵌套的for循环，根据以上法则，时间复杂度为O(m*n)。 7.在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数是____________。 从第i个元素（原来的）到第n个元素，每个元素后移一位，一共需要n+1-i次。 8.在一个具有n个结点的有序单链表中插入一个新结点，并让插入后的单链表仍然有序，则该操作的时间复杂性数量级为______。 找到节点位置，O(n)；单链表插入操作，O(n)；总的时间复杂度为O(n+n)=O(n)。 9.若用s[1]～s[n]作为两个顺序栈的共同存储空间，左右两个栈的栈顶分别为t1和t2，则判断某个栈是否可以插入新元素的条件是_________________。 当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。 此处判断某个栈是否可以插入新元素的条件是&t1!=&t2 10.设森林T中有三棵树，第一，二，三棵树的结点个数分别为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有____________个结点。 将一个森林转换为二叉树的具体方法是：① 将森林中的每棵树变为二叉树；② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。 个人认为此处可以填3个答案，n1-1或者n2-1或者n3-1。 11.在带权值有向图的邻接矩阵中，第i行上非零元素的个数等于_______________。 当节点Vi与某节点Vj相邻接,则A(i,j)取非0值。 12.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_____________。 散列（Hash）查找。
最新文章
热门文章
推荐阅读