【免费】数据结构往年考试题1资源-CSDN文库

数据结构

需积分: 0 67 浏览量 2022-08-08 23:19:52 上传评论收藏 226KB DOCX 举报

资源详情

资源评论

资源推荐

THU 数据结构历年期中期末题

第 1 题正误判断（凡交代未尽之处，皆以讲义及示例代码为准）

1. （ 1 ）对有序向量做 Fibonacci 查找，就最坏情况而言，成功查找所需的比较次数与失败查找相

等。

2.（ 1 ）

f(n) = ( ( ))g nO

，当且仅当

( ) ( ( ))g n f n= W

。

3.（ 0 ）若借助二分法查找确定每个元素的插入位置，向量的插入排序只需时间

( log )n nO

时间。

4.（ 1 ）RPN 中各操作数的相对次序，与原中缀表达式完全一致。

5.（ 1 ）对不含括号的中缀表达式求值时，操作法栈的容量可以固定为某一常数。

6.（ 0 ）无论有序向量或有序列表，最坏情况下均可在

(log )nO

时间内完成一次查找。

7.（ 0 ）只要是采用基于比较的排序算法，对任何输入序列都至少需要运行

(n log )nW

时间。

8.（ 0 ）对于同一有序向量，每次折半查找绝不会慢于顺序查找。

第 2 题多重选择

1.（ C ）共有几种栈混洗方案，可以使字符序列{‘x’,’o’,’o’,’o’,’x’}的输出保持原样？

A．12 B. 10 C. 6 D. 5

2．（ AD ）若

f(n) = (n ) ( ) ( )O g n O n=且

，则下列结论正确的是：

(n)+ ( ) = (n )f g n O

(n)/ ( ) = (n )f g n O

( ) = (f(n))g n O

(n)* ( ) = (n )f g n O

3．（ B ）对长度为

( ) 1n Fib k= -

的有向序列做 Fibonacci 查找。若个元素的数值等概率独立均匀分

布，且平均成功查找长度为 L，则失败平均查找长度为：

A．n(L-1)/(n-1) B. n(L+1)/(n+1) C. (n-1)L/n D. (n+1)L/n

4．（ A ）对长度为 Fib(12) – 1 = 143 的有序向量做 Fibonacci 查找，比较操作的次数至多为：

A．12 B. 11 C. 10 D. 9

5．（ D ）算法 g(n)的复杂度为

( )nQ

。若算法 f(n)中有 5 条调用 g(n)的指令，则 f(n)的复杂度为：

A．

( )nQ

( )O n

( )nW

D. 不确定

第 3 题估计以下函数 F(n)的复杂度（假定 int 类型字长无限，且递归不会溢出）

void F(int n) //O( sqrt(n) )

{

for (int i = 0, j = 0; i<n; i+=j, j++);

}

void F(int n) //O(loglogn )

{

for (int i = 1, r = 1; i<n; i<<=r, r<<=1);

}

void F(int n) //O( nlog(n))

{

for (int i=1; i<n; i++)

for (int j=0; j<n; j+=i);

}

void F(int n) //expected-O(nlog(n) )

{

for (int i=1; i<n; i++)

if(0 == rand()%i)

for (int j=1; j<n; j<<=1);

}

void F(int n) //O(logn* )

{

for (int i=1; i<n; i=1<<i);

}

void F(int n) //O(logn)

{

return (n<4) ? n : F(n>>1)+F(n>>2);

}

int F(int n) //O(n)

{

return (n==0) ? 1 : G(2, F(n-1));

}

int G(int n, int m)

{

return (m==0) ? 0 : n+G(n, m-1);

}

int F(int n) //O(n

{

return G(G(n-1));

}

int G(int n)

{

return (n==0) ? 0 : G(n-1)+2*n-1;

}

第 4 题分析与计算

1. 考察如下问题：任给 12 个互异的整数，且其中 10 个已组织为一个有序序列，现需要插入剩余

的两个已完成整体排序。若采用基于比较的算法（CBA），最坏情况下至少需要做几次比较？为

什么？

答：8 次。我们知道对于 CBA,我们可以将其涵盖于一棵比较树里边，而树的每一个节点可以代

表一次比较运算，树的分支可以代表算法下一步执行的方向。由此可以推算，树高则可以代表

比较的次数。

2. 向量的插入排序由 n 次迭代完成，逐次插入各元素。为插入第 k 个元素，最坏情况需要做 k 次移

动，最好情况则无需移动。从期望的角度来看，无需移动操作的迭代次数平均有多少次？为什

么？

假定个元素是等概率独立均匀分布的。

答：logn。调和级数

3. 现有一长度为 15 的有序向量 A[0…14]，个元素被成功查找的概率如下：

( 1)

P å =

1/1

1/3

1/1

1/6

1/1

3/1

1/1

1/6

若采用二分查找算法，试计算该结构的平均成功查找长度。

答：

4. 考察表达式求值算法。算法执行过程中的某时刻，若操作符栈中的括号多达 2010 个，则此时栈

的规模（含栈底的’\n’）至多可能多达？试说明理由，并示范性地画出当时栈中的内容。

答：3*2010+1+4 = 6035。

5. 阅读以下程序，试给出其中 ListReport()一句的输出结果（即当时序列 L 中个元素的数值）

剩余15页未读，继续阅读

评论收藏

内容反馈

咖啡碎冰冰

粉丝: 11
资源: 292

数据结构往年考试题1

评论0

最新资源

数据结构往年考试题1

评论0

各高校往年的数据结构试题

往年数据结构考题和答案

往年数据结构期末试题试卷

数据结构与算法试卷(往年复习题)

数据结构往年试题卷及答案

哈尔滨工业大学数据结构试题

考研数据结构往年试题及一些学习心得

湖南大学-数据结构-期末试题【2016-2019】.zip

C语言往年数据结构试题

往年深圳腾讯笔试题数据结构

中科院数据结构往年真题.zip

算法考试题往年.rar

西北工业大学数据结构历届考题

数据结构期末考试题

数据结构往年考研1800题包括完整答案

山东大学离散计组数据结构往年期末

福建工程学院-数据结构-期末考试复习题.pdf

2010年度数据结构期末考试卷

自考计算机科学 02331 数据结构 13年1月-19年4月 往年试题与答案.pdf

数据库系统工程师考试试题分类精解(2.数据结构与算法)

数据结构试题及答案 数据结构

算法与数据结构（C语言）试题与答案

BurpLoaderKeygen.jar.zip

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

OpenVAS GVM 中文翻译补丁

最新资源

自考计算机科学 02331 数据结构 13年1月-19年4月往年试题与答案.pdf

数据结构试题及答案数据结构