`
- 浏览:
501630 次
- 性别:
- 来自:
河北
-
---------------------------------------------------------------------------1. 两个二进制数的异或结果。 按位异或即可。---------------------------------------------------------------------------2. 递归函数最终会结束,那么这个函数一定(不定项选择): 1) 使用了局部变量 2) 有一个分支不调用自身 3) 使用了全局变量或者使用了一个或多个参数 2, 3---------------------------------------------------------------------------3. 以下函数的结果?int cal(int x){ if(x==0) return 0; else return x+cal(x-1);} x*(x+1)/2 (自然数求和)---------------------------------------------------------------------------4. 以下程序的结果是什么?void foo(int * a, int * b){ *a = *a+*b; *b = *a-*b; *a = *a-*b;}void main(){ int a=1, b=2, c=3; foo(&a,&b); foo(&b,&c); foo(&c,&a); printf("%d, %d, %d", a,b,c);} 1, 3, 2---------------------------------------------------------------------------5. 下面哪项不是链表优于数组的特点? 1. 方便删除 2. 方便插入 3. 长度可变 4. 存储空间小 4---------------------------------------------------------------------------6. T(n) = 25T(n/5)+n^2 的时间复杂度? O((n^2)*log(n)) 注:主定理。---------------------------------------------------------------------------7. n 个顶点,m 条边的全连通图,至少去掉几条边才能构成一棵树? m-(n-1) (n 个顶点的树边的条数为 n-1)---------------------------------------------------------------------------8. 正则表达式(01|10|1001|0110)*与下列哪个表达式一样? 1) (0|1)* 2) (01|01)* 3) (01|10)* 4) (11|01)* 5) (01|1)* 3---------------------------------------------------------------------------9. 如何减少换页错误? 1) 进程倾向于占用CPU 2) 访问局部性(locality of reference)满足进程要求 3) 进程倾向于占用I/O 4) 使用基于最短剩余时间(shortest remaining time)的调度机制 5) 减少页大小 2 (?)---------------------------------------------------------------------------10. 实现两个N*N矩阵的乘法,矩阵由一维数组表示。void matrix_multiply(int A[], int B[], int result[], int N){ for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { result[i*N+j] = 0; } } for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { for (int k = 0; k < N; ++k) { result[i*N+j] += A[i*N+k] * B[k*N+j]; } } }}/* 略微优化 */void matrix_multiply(int A[], int B[], int result[], int N){ for (int i = 0; i < N * N; i += N) { for (int j = 0; j < N; ++j) { result[i+j] = 0; } } for (i = 0; i < N * N; i += N) { for (j = 0; j < N; ++j) { int t = 0; for (ia = i, ib = j; ib < N * N; ++ia, ib += N) { t += a[ia] * b[ib]; } result[i+j] = t; } }}---------------------------------------------------------------------------11. 找到单向链表中间那个元素,如果有两个则取前面一个。#include <stddef.h>struct listtype{ int data; struct listtype * next;};typedef struct listtype * list;/* Find the middle element of the singly linked list sll. */list find_middle(list sll){ list slow = sll; list fast = sll; if (NULL == fast) { return NULL; } while (1) { if (NULL == fast->next || NULL == fast->next->next) { return slow; } slow = slow->next; fast = fast->next->next; /* Prevent that there is a loop in the linked list. */ if (fast == slow) { return NULL; } }}---------------------------------------------------------------------------12. 长度为 N 的整数数组,找出其中任意(N-1)个乘积最大的那一组,只能用乘法,不可以用除法。要求对算法的时间复杂度和空间复杂度作出分析,不要求写程序。 令这 N 个数的乘积为 P, 1) 如果 P<0,则剔除其中最大的负整数即可; 2) 如果 P=0, 2.1) 若这 N 个数中有且仅有一个为“0”。若其他数之积为正,则剔除“0”;否则剔除任意一个非零数; 2.2) 若这 N 个数中至少有两个为“0”,则随便剔除一个数均可; 3) 如果 P>0,如果有正数,则剔除其中最小的正整数即可;否则,剔除最小的负整数。 时间复杂度:遍历数组,获得正整数个数 cp,负整数个数 cn,0 的个数 cz,需要 O(N) 时间;找被剔除的数最坏情况下需要 O(N) 时间。输出结果需要 O(N) 时间。因此,时间复杂度为 O(N)。 空间复杂度:数组存储需要 O(N) 空间,cp, cn, cz 和被剔除的数的下标各需要 O(1) 空间。因此,空间复杂度为 O(N)。---------------------------------------------------------------------------
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
上海交大培训试题 分两个部分
上海交通大学电路基本理论2006版考研电路基本理论
上海交通大学2006硕士研究生入学考试试题 计算机基础I 数据结构试题70分
上海交大数据结构课程的习题解答,关于二叉树的一道习题
上海交通大学一九九六年研究生入学考试试题 试题名称:信号与系统(含数字信号处理)
资源包括上海交通大学431金融真题,考生考完第二天回忆整理而成,同时还有一些报考建议,上海交大金融专硕考研专业课存在严重的信息差,这份文件非常有价值!
上海交通大学电路真题,附带标准答案 考电气地 可以拿去看看
上海交大《计算方法》考博真题
该文件是用于上海交大软件学院夏令营机试题目,大家可以借鉴该题目进行相应的练习,不限语言
上海交通大学05-07年上机真题,内附答案,为那些打算考研或保研到上海交大同学准备
上海交大编译原理习题上海交通大学出版1998
上海交通大学治理学院金融工程学习题.docx上海交通大学治理学院金融工程学习题.docx上海交通大学治理学院金融工程学习题.docx上海交通大学治理学院金融工程学习题.docx上海交通大学治理学院金融工程学习题.docx上海...
上海交大数学系自己编写的教材,很好的教材,尤其要推荐给学工科的同学
上海交大往年考博真题,希望对广大考博学子有所帮助,加油。
上海交通大学期末考试题,C++ zhuanye de d de de
上海交通大学线性代数试卷.pdf
上海交通大学高等数学试题解析,适合考研的兄弟姐妹
上海交通大学线性代数教材上海交通大学线性代数教材上海交通大学线性代数教材上海交通大学线性代数教材
上海交通大学上海交通大学1999年秋季博士生入学考试英语试题