文章目录
C/C++笔试练习选择部分（1）时间复杂度（2）链表的性质（3）链表的性质（4）链栈的插入（5）队列的性质（6）二叉树的度（7）平衡二叉查找树（8）向上调整算法（9）哈希表的查找（10）外部排序
编程题 day23微信红包计算字符串的距离
C/C++笔试练习
选择部分
（1）时间复杂度
下列代码的时间复杂度为（ ）
for(int i=0;i { for(int j=0;j { a[i][j]=i*j; } } A. O(n2) B. O(m2) C. O(n*m) D. O(n+m) 答案：C 时间复杂度的计算基于嵌套循环的次数。外层循环执行 m 次，内层循环执行 n 次，因此总的时间复杂度是 mn，即 O(nm)。 （2）链表的性质 下列关于线性链表的叙述中，正确的是（ ） A. 各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致 B. 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续 C. 进行插入与删除时，不需要移动表中的元素 D. 以上说法均不正确 答案：C 线性链表的特点是数据元素在内存中的存储空间可以不连续，且各数据结点的存储顺序与逻辑顺序可以不一致。但插入与删除时不需要移动表中的元素，只需要改变指针 （3）链表的性质 下列描述的不是链表的优点是（ ） A. 逻辑上相邻的结点物理上不必邻接 B. 插进、删除运算操纵方便，不必移动结点 C. 所需存储空间比顺序表节省 D. 无需事先估计存储空间的大小 答案：C 链表的插入和删除操作方便，不需要移动结点。当需要在链表中插入或删除元素时，只需要改变指针的指向，不需要移动整个链表中的元素。 但是链表需要额外的空间来存储指针，而顺序表则不需要。 （4）链栈的插入 向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时,应执行() A. h->next=s; B. s->next=h; C. s->next=h;h->next=s; D. s->next=h->next;h->next=s; 答案：D 给定一个栈顶指针为h的链栈，我们要将指针s所指的结点插入到链栈的顶部，我们可以执行以下操作： 将新结点的next指针指向当前栈顶结点的下一个结点，即 s->next = h->next，将栈顶结点的next指针指向新结点，即 h->next = s。 （5）队列的性质 队列{a,b,c,d,e}依次入队，允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的出队序列是（） A. b， a， c， d， e B. d， b， a， c， e C. d， b， c， a， e D. e， c， b， a， d 答案：C 队列是一种先进先出（First In First Out，FIFO）的数据结构。这意味着第一个进入队列的元素将是第一个出队的元素。 加以题目条件简单模拟，对于C项，如果队列顺序为a，b，c，d，先让d出队列，此时为a，b，c则b无法出队列。如果队列顺序为c，a，b，d，d出队列之后，b可以继续出队列，但是接下来的c就无法出队列了。 （6）二叉树的度 若一棵二叉树具有12个度为2的结点，6个度为1的结点，则度为0的结点个数是（） A. 10 B. 11 C. 13 D. 不确定 答案：C 二叉树的公式:n0=n2+1，代入即可得到n0=13。 （7）平衡二叉查找树 下列各树形结构中,哪些是平衡二叉查找树: 答案：C 平衡二叉查找树的左右子树高度差不大于1，且左子树的值小于根节点，右子树的值大于根节点。 A和B的左右子树高度差都大于1，D的数据6小于7，应该在7节点的左子树，位置错误。 （8）向上调整算法 已知关键字序列5,8,12,19,28,20,15,22是最小堆，插入关键字3，调整后得到的最小堆是（） A. 3,8,12,5,20,15,22,28,19 B. 3,5,12,19,20,15,22,8,28 C. 3,12,5,8,28,20,15,22,19 D. 3,5,12,8,28,20,15,22,19 答案：D （9）哈希表的查找 采用哈希表组织100万条记录，以支持字段A快速查找，则（） A. 理论上可以在常数时间内找到特定记录 B. 所有记录必须存在内存中 C. 拉链式哈希曼最坏查找时间复杂度是O（n） D. 哈希函数的选择跟A无关 答案：C 对于A如果在查找的时候，哈希冲突比较多，我们就需要查找n次才可以找到我们需要的记录，此时的时间复杂度就会是O(n)。我们可以使用磁盘来记录数据。对于C，哈希表存储的最坏情况时，所有的数据都冲突映射到了一个地方，此时的查找时间复杂度就是O(n)。 好的哈希函数可以减少哈希冲突。 （10）外部排序 假设你只有100Mb的内存，需要对1Gb的数据进行排序，最合适的算法是（） A. 归并排序 B. 插入排序 C. 快速排序 D. 冒泡排序 答案：A 外部排序使用归并排序。 编程题 day23 微信红包 微信红包 解题思路：本题两种思路，第一种排序思路，如果一个数出现次数超过一半了，排序过后，必然排在中间，则最后遍历整个数组查看是否符合即可。第二种思路可以用map统计每个数字出现的次数，最后判断有没有超过一半的数字。 class Gift { public: int getValue(vector { sort(gifts.begin(), gifts.end()); //超过一半的数排序之后必然排在中间 int middle = gifts[n / 2]; int count = 0; for (int i = 0; i < n; i++) { //统计排在中间的数的个数 if (gifts[i] == middle) { count++; } } //如果个数大于一半，则存在超过一半的数 if (count > n / 2) return middle; else return 0; } }; /*思路二：map统计 class Gift { public: int getValue(vector { map int middle = gifts.size() / 2; for (const auto& e : gifts) { ++count[e]; } for (const auto& e : count) { if (e.second >= middle) return e.first; } return 0; } }; */ 计算字符串的距离 计算字符串的距离 解题思路：本题需要用动态规划解题 状态： 子状态：word1的前1，2，3，…m个字符转换成word2的前1，2，3，…n个字符需要的编辑距离。 F(i,j):word1的前i个字符于word2的前j个字符的编辑距离 状态递推： F(i,j) = min { F(i-1,j）+1, F(i,j-1) +1, F(i-1,j-1) +(w1[i]==w2[j]?0:1) } 上式表示从删除，增加和替换操作中选择一个最小操作数 F(i-1,j): w1[1,…,i-1]于w2[1,…,j]的编辑距离，删除w1[i]的字符—>F(i,j) F(i,j-1): w1[1,…,i]于w2[1,…,j-1]的编辑距离，增加一个字符—>F(i,j) F(i-1,j-1): w1[1,…,i-1]于w2[1,…,j-1]的编辑距离，如果w1[i]与w2[j]相同， 不做任何操作，编辑距离不变，如果w1[i]与w2[j]不同，替换w1[i]的字符为w2[j]—>F(i,j) 初始化： 初始化一定要是确定的值，如果这里不加入空串，初始值无法确定 F(i,0) = i :word与空串的编辑距离，删除操作 F(0,i) = i :空串与word的编辑距离，增加操作 返回结果：F(m,n)。 #include #include #include using namespace std; int minDistance(const string& str1, const string& str2) { // word与空串之间的编辑距离为word的长度 if (str1.empty() || str2.empty()) return max(str1.size(), str2.size()); int len1 = str1.size(); int len2 = str2.size(); vector //初始化距离 for (int i = 0; i <= len1; ++i) f[i][0] = i; for (int j = 0; j <= len2; ++j) f[0][j] = j; for (int i = 1; i <= len1; ++i) { for (int j = 1; j <= len2; ++j) { // F(i,j) = min { F(i-1,j）+1, F(i,j-1) +1, F(i-1,j-1) + //(w1[i]==w2[j]?0:1) } // 判断word1的第i个字符是否与word2的第j个字符相等 if (str2[j - 1] == str1[i - 1]) { f[i][j] = 1 + min(f[i - 1][j], f[i][j - 1]); //由于字符相同，所以距离不发生变化 f[i][j] = min(f[i][j], f[i - 1][j - 1]); } else { f[i][j] = 1 + min(f[i - 1][j], f[i][j - 1]); //由于字符不相同，所以距离+1 f[i][j] = min(f[i][j], 1 + f[i - 1][j - 1]); } } } return f[len1][len2]; } int main() { string str1, str2; while (cin >> str1 >> str2) cout << minDistance(str1, str2) << endl; return 0; } 推荐链接
您阅读本篇文章共花了：
发表评论