2024年5月3日发(作者：终娴雅)

题目1：一条小溪上7块石头，如图所示：（图就是下面的链接）

/app_uploads/jinder22/20081220/?d=20403

分别有六只青蛙：A，B，C，D，E，F。A，B，C三只蛙想去右岸，它们只会从左向右跳；D，E，F三只蛙想去左岸，它们只会从右向

左跳。青蛙每次最多跳到自己前方第2块石头上。请问最少要跳几次所有青蛙上岸。写出步骤。

题目2：Which of the choices below correctly describes the amount of time used by the following code:（下面那个选项

正确地描述了代码运行的调度次数）

n=10;

for(i=1; i

for(j=1; j

for(k=1; k

x = x +1;

A Θ(n^3)

B Θ(n2logn)

C Θ(n(log n)2)

D Θ(n log n)

E Θ((logn)2)

题目3：Give a one-line C expression to test whether a number is a power of?（这句话不知道咋翻译）

题目4：What is wrong with the following code?（下面代码哪错了）

char *p;

*p = malloc(10);

题目5：Write a c++ function to take two sorted single linked lists as parameters and marge them into one then return

it (Please write data structure first)(请写一个C++程序对两个排好序的单链表合成一个大的单链表)

S1.1->4->5, S2:2->3->6, result="1->2->3->4->5->6"

题目6：Write a function to get the second maximum number in an integer array.（请写程序返回一个数组中第2大的数）

int getsecond(int a [])

题目7：Write a c++ program that will delete itself after execution.（写一个程序，该程序执行完后自己删除自己）

题目8：What is the difference between calloc and malloc?（calloc malloc区别是什么？）

题目9：what's wrong with the call fopen("c:newdirfile dat"."r")?

题目10：A quad-tree, starting from the root node, could consist of many nodes: leaf-node and non-leaf node. Each

non-leaf node may have 1 to 4 child nodes; each node has an internal value V, if not null, which would refer to any node

in the same quad-tree. Hierarchically, depth of node describes the distance between a node in a tree and the tree’s root

node, the farther the distance is, the deeper the node is at in the tree. The goal is to find all the nodes in the quad-tree

which fulfills the condition: the value of node A refers to a node B in the same tree, where the depth of node A is larger

than the depth of node B. The input would be a data structure representing the quad-tree; the output would be a data

structure representing the list of nodes fulfilling the conditions. （四叉树由许多个节点组成，其起点是根节点。节点有两种：

叶子节点，非叶子节点，其中每个非叶子节点又可分出1到4个子节点。每一节点都包含其内在值V。如果这个值非空，则可以表示同

一四叉树上任一节点的值。从等级上划分，节点的深度表明节点与根节点之间的距离：距离越远，节点的深度越深。目的是找出四叉树

上所有符合以下条件的节点：在同一树上，节点A 的值引用节点B，但其深度要大于节点B的深度。输入的数据结构以四叉树形式呈现，

输出的数据结构以链表呈现）

Q1: Describe how you will solve the problem and explain why you pick the solution. The best answer should consider

multiple solutions and choose the optimal one in terms of time and space complexity, and explain why you choose this

one. （Q1，说明你如何解决这个问题并解释你为什么采取那种解决方式。最好的回答应是在多种解决方案中根据时空的复杂程度选择

最佳的一种并解释你为什么选择该项）

Q2: Implement the solution you have chose in the previous question in any programming language. A function is

required for the code you write so that others can call it. You should define the major data structures you are going to

use in the function. （把你在前一问题中选择的解决方法运用于任一程序语言中。要求你的函数具有一种功能，以便其他人能对调用

它？你需要界定你将在这一函数中使用的主要数据结构）

Q3: Provide list sufficient test cases that can validate the code you write in Q2 working correctly as expected. The best

answer should consider various typical cases for different usages by function callers, including common cases, boundary

cases, error case, etc.（提供一组有效的测试用例证明你在问题2中的编码达到了预期目标。最好的回答应考虑到函数调用者，对不

同类型实例的不同使用，这些实例包括普通实例，边缘实例和错误实例等）

2024年5月3日发(作者：终娴雅)

题目1：一条小溪上7块石头，如图所示：（图就是下面的链接）

/app_uploads/jinder22/20081220/?d=20403

分别有六只青蛙：A，B，C，D，E，F。A，B，C三只蛙想去右岸，它们只会从左向右跳；D，E，F三只蛙想去左岸，它们只会从右向

左跳。青蛙每次最多跳到自己前方第2块石头上。请问最少要跳几次所有青蛙上岸。写出步骤。

题目2：Which of the choices below correctly describes the amount of time used by the following code:（下面那个选项

正确地描述了代码运行的调度次数）

n=10;

for(i=1; i

for(j=1; j

for(k=1; k

x = x +1;

A Θ(n^3)

B Θ(n2logn)

C Θ(n(log n)2)

D Θ(n log n)

E Θ((logn)2)

题目3：Give a one-line C expression to test whether a number is a power of?（这句话不知道咋翻译）

题目4：What is wrong with the following code?（下面代码哪错了）

char *p;

*p = malloc(10);

题目5：Write a c++ function to take two sorted single linked lists as parameters and marge them into one then return

it (Please write data structure first)(请写一个C++程序对两个排好序的单链表合成一个大的单链表)

S1.1->4->5, S2:2->3->6, result="1->2->3->4->5->6"

题目6：Write a function to get the second maximum number in an integer array.（请写程序返回一个数组中第2大的数）

int getsecond(int a [])

题目7：Write a c++ program that will delete itself after execution.（写一个程序，该程序执行完后自己删除自己）

题目8：What is the difference between calloc and malloc?（calloc malloc区别是什么？）

题目9：what's wrong with the call fopen("c:newdirfile dat"."r")?

题目10：A quad-tree, starting from the root node, could consist of many nodes: leaf-node and non-leaf node. Each

non-leaf node may have 1 to 4 child nodes; each node has an internal value V, if not null, which would refer to any node

in the same quad-tree. Hierarchically, depth of node describes the distance between a node in a tree and the tree’s root

node, the farther the distance is, the deeper the node is at in the tree. The goal is to find all the nodes in the quad-tree

which fulfills the condition: the value of node A refers to a node B in the same tree, where the depth of node A is larger

than the depth of node B. The input would be a data structure representing the quad-tree; the output would be a data

structure representing the list of nodes fulfilling the conditions. （四叉树由许多个节点组成，其起点是根节点。节点有两种：

叶子节点，非叶子节点，其中每个非叶子节点又可分出1到4个子节点。每一节点都包含其内在值V。如果这个值非空，则可以表示同

一四叉树上任一节点的值。从等级上划分，节点的深度表明节点与根节点之间的距离：距离越远，节点的深度越深。目的是找出四叉树

上所有符合以下条件的节点：在同一树上，节点A 的值引用节点B，但其深度要大于节点B的深度。输入的数据结构以四叉树形式呈现，

输出的数据结构以链表呈现）

Q1: Describe how you will solve the problem and explain why you pick the solution. The best answer should consider

multiple solutions and choose the optimal one in terms of time and space complexity, and explain why you choose this

one. （Q1，说明你如何解决这个问题并解释你为什么采取那种解决方式。最好的回答应是在多种解决方案中根据时空的复杂程度选择

最佳的一种并解释你为什么选择该项）

Q2: Implement the solution you have chose in the previous question in any programming language. A function is

required for the code you write so that others can call it. You should define the major data structures you are going to

use in the function. （把你在前一问题中选择的解决方法运用于任一程序语言中。要求你的函数具有一种功能，以便其他人能对调用

它？你需要界定你将在这一函数中使用的主要数据结构）

Q3: Provide list sufficient test cases that can validate the code you write in Q2 working correctly as expected. The best

answer should consider various typical cases for different usages by function callers, including common cases, boundary

cases, error case, etc.（提供一组有效的测试用例证明你在问题2中的编码达到了预期目标。最好的回答应考虑到函数调用者，对不

同类型实例的不同使用，这些实例包括普通实例，边缘实例和错误实例等）